SLAM (метод)

Переможець змагань DARPA Grand Challenge^[en] — STANLEY^[en], використовував SLAM, як елемент своєї автономної системи водіння.

При розв'язуванні задач навігації і картографії у робототехніці, одночасна локалізація і картографування (англ. simultaneous localization and mapping — SLAM) є алгоритмічною обчислювальною задачею побудови і оновлення мапи невідомого оточення з одночасним відстежуванням місцеположення рухаючись по ньому. Хоча це схоже на задачу «курка чи яйце?», існує декілька алгоритмів, що розв'язують її, щонайменше приблизно, в скінченний час для певних умов. До популярних методів розв'язування належать фільтр часток^[en], розширений фільтр Калмана і GraphSLAM.

Алгоритми SLAM обмежуються наявними ресурсами, таким чином не можуть бути абсолютно досконалими, бо досягають оперативної доступності. Опубліковані методи і підходи реалізовані в безпілотних автомобілях, безпілотних літаючих засобах, автономних підводних апаратах, планетоходах, згодом виникли в побутових роботах і навіть всередині людського тіла.^[1]

Постановка задачі[ред. | ред. код]

Дана послідовність даних спостереження сенсору $o_{t}$ за дискретні проміжки часу $t$ , задачею SLAM є розрахувати і визначити розташування агента $x_{t}$ і мапу оточення $m_{t}.$ Всі величини зазвичай ймовірнісні, тому необхідно обчислити:

P(m_{t},x_{t}|o_{1:t})

Застосування правила Баєса дає основу для послідовного оновлення апостеріорного розташування, при даній мапі і функції переходу $P(x_{t}|x_{t-1}),$

P(x_{t}|o_{1:t},m_{t})=\sum _{m_{t-1}}P(o_{t}|x_{t},m_{t})\sum _{x_{t-1}}P(x_{t}|x_{t-1})P(x_{t-1}|m_{t},o_{1:t-1})/Z.

Аналогічно мапа може оновлюватися послідовно наступним шляхом

P(m_{t}|x_{t},o_{1:t})=\sum _{x_{t}}\sum _{m_{t}}P(m_{t}|x_{t},m_{t-1},o_{t})P(m_{t-1},x_{t}|o_{1:t-1},m_{t-1}).

Як для більшості задач наближення, рішення можна знайти при наближенні двох змінних, до локального оптимального рішення, шляхом почергового оновлення двох рівнянь у формі ЕМ-алгоритму.

Алгоритми[ред. | ред. код]

До статистичних методів, що використовуються для задач апроксимації наведених вище, належать: фільтр Калмана, фільтр часток^[en] (який є методом Монте-Карло) і узгоджене сканування діапазонних даних. Вони дозволяють визначити оцінку функції апостеріорної ймовірності для позиції робота і параметрів мапи. Техніки оцінювання приналежності до множини^[en] в основному засновуються на поширенні сталого інтервалу^[en].^[2]^[3] Вони забезпечують множину, яка містить позицію робота і множину апроксимації мапи. Налаштування пучка є наступною популярною технікою у SLAM, який використовує дані зображень поєднані з оцінками розташування робота і орієнтирів на місцевості, тим самим підвищуючи точність мапи. Вона використовується в комерційних SLAM системах, таких як Проект Tango [Архівовано 16 березня 2014 у Wayback Machine.] компанії Google.

Нові алгоритми SLAM досі потребують активного дослідження і пошуку, і часто обумовлені різними вимогами і припущеннями щодо типів карт, давачів і моделей. Більшість SLAM систем можна розглядати як комбінації виборів кожного з цих аспектів.

Картографування[ред. | ред. код]

Побудова топологічних мап це метод представлення довколишнього світу, який узагальнює структуру (тобто, топологію) оточення замість створення геометрично точної мапи. Топологічні методи SLAM використовуються для підвищення загальної узгодженості метричних алгоритмів SLAM.^[4]

На противагу тому, для топологічного представлення світу існують мапи у вигляді поверхонь, які використовують масиви оцифрованих елементів (зазвичай квадратних, або гексагональних клітин), і роблять припущення яка клітина зайнята в конкретний момент. Зазвичай клітини вважаються статистично незалежними, аби спростити обчислення. Згідно цього припущення, $P(m_{t}|x_{t},m_{t-1},o_{t})$ приймає значення 1, якщо клітини нової карти узгоджені із спостереженням $o_{t}$ на позиції $x_{t}$ і 0, якщо неузгоджені.

Реалізація[ред. | ред. код]

Різноманітні алгоритми SLAM реалізовані у відкритих бібліотеках Robot Operating System, які часто використовуються з Point Cloud Library для побудови 3D карт або візуальних ефектів у OpenCV.

Список методів SLAM[ред. | ред. код]

Список відомих реалізацій методів SLAM:

EKF SLAM
FastSLAM 1.0
FastSLAM 2.0
L-SLAM^[5] (Код для Matlab) [Архівовано 11 червня 2018 у Wayback Machine.]
GraphSLAM
Occupancy Grid SLAM^[6]
DP-SLAM
Parallel Tracking and Mapping (PTAM) [Архівовано 20 жовтня 2016 у Wayback Machine.]^[7]
LSD-SLAM^[8] (доступно в відкритому коді)
ORB-SLAM [Архівовано 27 вересня 2016 у Wayback Machine.]^[9] (доступно в відкритому коді)
ORB-SLAM2
MonoSLAM
CoSLAM [Архівовано 6 квітня 2017 у Wayback Machine.]^[10]
SeqSlam^[11]

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

↑ Mountney, P.; Stoyanov, D.; Davison, A.; Yang, G-Z. (2006). Simultaneous Stereoscope Localization and Soft-Tissue Mapping for Minimal Invasive Surgery. MICCAI. 1: 347—354. doi:10.1007/11866565_43. Архів оригіналу за 12 січня 2017. Процитовано 30 липня 2010.
↑ Jaulin, L. (2009). A nonlinear set-membership approach for the localization and map building of an underwater robot using interval constraint propagation (PDF). IEEE Transactions on Robotics. Архів оригіналу (PDF) за 5 жовтня 2016. Процитовано 3 жовтня 2016.
↑ Jaulin, L. (2011). Range-only SLAM with occupancy maps; A set-membership approach (PDF). IEEE Transactions on Robotics. Архів оригіналу (PDF) за 5 жовтня 2016. Процитовано 3 жовтня 2016.
↑ Cummins, Mark; Newman, Paul (June 2008). FAB-MAP: Probabilistic localization and mapping in the space of appearance (PDF). The International Journal of Robotics Research. 27 (6): 647—665. doi:10.1177/0278364908090961. Архів оригіналу (PDF) за 12 травня 2014. Процитовано 23 липня 2014.
↑ Zikos, Nikos; Petridis, Vassilios (2014), 6-DoF Low Dimensionality SLAM (L-SLAM), Journal of Intelligent & Robotic Systems, Springer: 1—18, doi:10.1007/s10846-014-0029-6, ISSN 0921-0296
↑ Thrun, S.; Burgard, W.; Fox, D. (2005). Probabilistic Robotics. Cambridge: The MIT Press. ISBN 0-262-20162-3.
↑ G. Klein and D. Murray (2007). Parallel Tracking and Mapping for Small AR Workspaces. International Symposium on Mixed and Augmented Reality (ISMAR). Архів оригіналу (PDF) за 6 грудня 2016. Процитовано 4 жовтня 2016.
↑ J. Engel and T. Schops and D. Cremers (2014). LSD-SLAM: Large-Scale Direct Monocular SLAM (PDF). European Conference on Computer Vision (ECCV). Архів оригіналу (PDF) за 22 жовтня 2014. Процитовано 4 жовтня 2016.
↑ R. Mur-Artal and J. M. M. Montiel and J. D. Tardós (2015). ORB-SLAM: A Versatile and Accurate Monocular SLAM System. IEEE Transactions on Robotics. 31 (5): 1147—1163. arXiv:1502.00956. doi:10.1109/TRO.2015.2463671. ISSN 1552-3098.
↑ D. Zou and P. Tan (2013). CoSLAM: Collaborative Visual SLAM in Dynamic Environments (PDF). IEEE Trans. on Pattern Analysis and Machine Intelligence. IEEE. Архів оригіналу (PDF) за 5 липня 2016. Процитовано 4 жовтня 2016.
↑ Michael J. Milford and Gordon. F. Wyeth. SeqSLAM: Visual Route-Based Navigation for Sunny Summer Days and Stormy Winter Nights. Proc. of Intl. Conf. on Robotics and Automation.

[Mountney2006-1] Mountney, P.; Stoyanov, D.; Davison, A.; Yang, G-Z. (2006). Simultaneous Stereoscope Localization and Soft-Tissue Mapping for Minimal Invasive Surgery. MICCAI. 1: 347—354. doi:10.1007/11866565_43. Архів оригіналу за 12 січня 2017. Процитовано 30 липня 2010.

[2] Jaulin, L. (2009). A nonlinear set-membership approach for the localization and map building of an underwater robot using interval constraint propagation (PDF). IEEE Transactions on Robotics. Архів оригіналу (PDF) за 5 жовтня 2016. Процитовано 3 жовтня 2016.

[3] Jaulin, L. (2011). Range-only SLAM with occupancy maps; A set-membership approach (PDF). IEEE Transactions on Robotics. Архів оригіналу (PDF) за 5 жовтня 2016. Процитовано 3 жовтня 2016.

[cummins2008-4] Cummins, Mark; Newman, Paul (June 2008). FAB-MAP: Probabilistic localization and mapping in the space of appearance (PDF). The International Journal of Robotics Research. 27 (6): 647—665. doi:10.1177/0278364908090961. Архів оригіналу (PDF) за 12 травня 2014. Процитовано 23 липня 2014.

[Zikos2014-5] Zikos, Nikos; Petridis, Vassilios (2014), 6-DoF Low Dimensionality SLAM (L-SLAM), Journal of Intelligent & Robotic Systems, Springer: 1—18, doi:10.1007/s10846-014-0029-6, ISSN 0921-0296

[Trun2005-6] Thrun, S.; Burgard, W.; Fox, D. (2005). Probabilistic Robotics. Cambridge: The MIT Press. ISBN 0-262-20162-3.

[Klein07-7] G. Klein and D. Murray (2007). Parallel Tracking and Mapping for Small AR Workspaces. International Symposium on Mixed and Augmented Reality (ISMAR). Архів оригіналу (PDF) за 6 грудня 2016. Процитовано 4 жовтня 2016.

[Engel14-8] J. Engel and T. Schops and D. Cremers (2014). LSD-SLAM: Large-Scale Direct Monocular SLAM (PDF). European Conference on Computer Vision (ECCV). Архів оригіналу (PDF) за 22 жовтня 2014. Процитовано 4 жовтня 2016.

[Mur-Artal15-9] R. Mur-Artal and J. M. M. Montiel and J. D. Tardós (2015). ORB-SLAM: A Versatile and Accurate Monocular SLAM System. IEEE Transactions on Robotics. 31 (5): 1147—1163. arXiv:1502.00956. doi:10.1109/TRO.2015.2463671. ISSN 1552-3098.

[Danping13-10] D. Zou and P. Tan (2013). CoSLAM: Collaborative Visual SLAM in Dynamic Environments (PDF). IEEE Trans. on Pattern Analysis and Machine Intelligence. IEEE. Архів оригіналу (PDF) за 5 липня 2016. Процитовано 4 жовтня 2016.

[Milford-11] Michael J. Milford and Gordon. F. Wyeth. SeqSLAM: Visual Route-Based Navigation for Sunny Summer Days and Stormy Winter Nights. Proc. of Intl. Conf. on Robotics and Automation.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

SLAM (метод)

Зміст

Постановка задачі[ред. | ред. код]

Алгоритми[ред. | ред. код]

Картографування[ред. | ред. код]

Реалізація[ред. | ред. код]

Список методів SLAM[ред. | ред. код]

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

Навігаційне меню

SLAM (метод)

Постановка задачі[ред. | ред. код]

Алгоритми[ред. | ред. код]

Картографування[ред. | ред. код]

Реалізація[ред. | ред. код]

Список методів SLAM[ред. | ред. код]

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

Навігаційне меню

Пошук