DP-SLAM

DP-SLAM (англ. Distributed Particle — Simultaneous Localization And Mapping) — один из подходов к решению задачи позиционирования подвижного робота методом SLAM, который использует относительно несложный фильтр частиц над массивом карт и положений робота. Этот метод был предложен исследователями университета Дьюка (Северная Каролина) в их публикации для Международной объединенной конференции по искусственному интеллекту IJCAI (англ. International Joint Conferences on Artificial Intelligence) в 2003 году^[1]. Через год на Международной конференции по робототехнике и автоматизации (англ. IEEE International Conference on Robotics and Automation) ими была представлена модернизированная версия алгоритма DP-SLAM 2.0^[2].

Описание методаПравить

Применение метода стало возможным благодаря резкому удешевлении современной лазерной дальномерной техники и значительному прогрессу, достигнутому в области многочастичной фильтрации. В ходе работы создателям DP-SLAM удалось избежать применения затратных по времени EM-алгоритмов для многопроходного построения предварительных эвристических оценок базовой схемы SLAM. Взяв за отправную точку архитектуру метода FastSLAM в вычислительном алгоритме DP-SLAM удалось отказаться от использования маркеров-ориентиров, выделенных в окружающей робота среде. Такая редукция вычислительной схемы автоматически устранила широкий класс проблем, связанных с ассоциативностью экспериментальных данных и с априорными предположениями о маркерах. Однако издержкой такого подхода стала необходимость манипулировать и обновлять в памяти значительные объёмы информации с сотнями участков локально-промеренных карт местности. Тем не менее, представленный алгоритм в наихудшем случае продемонстрировал логоквадратичную сложность в зависимости от количества отсчётов и линейную сложность в зависимости от обозреваемой лазерным сенсором площади^[1].

Структурное представление картыПравить

Карта представляется в виде сетки с заполнением ячеек, занятых препятствиями.

Хранить такую карту удобно в виде массива, где элементы, отражающие положение препятствий, имеют значение 1, а все остальные — 0.

Оценка методаПравить

Метод вызвал определённый интерес среди специалистов по прикладной математике и робототехнике. В ряде научных публикаций его эффективность — в сочетании с обновляемыми графами^[en]^* типа «генеалогическое древо» для представления оцифрованных карт местности — получила весьма высокие оценки^[3]. В 2007 году, благодаря наличию в открытом доступе детальной документации и относительной простоте реализации, характеристики метода DP-SLAM стали объектом скрупулёзного сопоставления с некоторыми другими вариантами (TEAMBOTICA и 6D-SLAM) общего алгоритма SLAM^[4]. В 2010 году группа французских исследователей обратила внимание, что программное воплощение алгоритмической базы DP-SLAM потребует не более, чем 200 строк кода на языке программирования Си^[5].

ПримечанияПравить

↑ ¹ ² A. Eliazar, R. Parr. DP-SLAM: Fast, Robust Simultaneous Localization and Mapping Without Predetermined Landmarks : [англ.]. — IJCAI. — 2003.
↑ A. Eliazar, R. Parr. DP-SLAM 2.0 : [англ.]. — IEEE International Conference on Robotics and Automation. — 2004. — doi:10.1109/ROBOT.2004.1308006.
↑ S. Thrun, J. Leonard. Simultaneous Localization and Mapping // Springer Handbook of Robotics / B. Siciliano, O. Khatib. — Springer, 2008. — P. 883. — ISBN 978-3-540-23957-4.
↑ R.Ouellette, K. Hirasawa. A comparison of SLAM implementations for indoor mobile robots : [англ.]. — IEEE/RSJ International Conference on Intelligent Robots and Systems. — 2007. — P. 1479—1484. — doi:10.1109/iros.2007.4399575.
↑ B. Steux, O. Hamzaoui. tinySLAM : a SLAM Algorithm in less than 200lines C-Language Program : [англ.]. — 11th International Conference on Control Automation Robotics & Vision. — 2010. — P. 1975—1979. — doi:10.1109/ICARCV.2010.5707402.

СсылкиПравить

Официальный сайт проекта DP-SLAM

[eliazar-1] ¹ ² A. Eliazar, R. Parr. DP-SLAM: Fast, Robust Simultaneous Localization and Mapping Without Predetermined Landmarks : [англ.]. — IJCAI. — 2003.

[2] A. Eliazar, R. Parr. DP-SLAM 2.0 : [англ.]. — IEEE International Conference on Robotics and Automation. — 2004. — doi:10.1109/ROBOT.2004.1308006.

[3] S. Thrun, J. Leonard. Simultaneous Localization and Mapping // Springer Handbook of Robotics / B. Siciliano, O. Khatib. — Springer, 2008. — P. 883. — ISBN 978-3-540-23957-4.

[4] R.Ouellette, K. Hirasawa. A comparison of SLAM implementations for indoor mobile robots : [англ.]. — IEEE/RSJ International Conference on Intelligent Robots and Systems. — 2007. — P. 1479—1484. — doi:10.1109/iros.2007.4399575.

[5] B. Steux, O. Hamzaoui. tinySLAM : a SLAM Algorithm in less than 200lines C-Language Program : [англ.]. — 11th International Conference on Control Automation Robotics & Vision. — 2010. — P. 1975—1979. — doi:10.1109/ICARCV.2010.5707402.

[1]

[2]

[3]

[4]

[5]