Просмотр кода страницы DP-SLAM

{{содержание справа}}
'''DP-SLAM''' ({{lang-en|Distributed Particle — Simultaneous Localization And Mapping}}) — один из подходов к решению задачи позиционирования подвижного робота методом ''[[SLAM (метод)|SLAM]]'', который использует относительно несложный [[Многочастичный фильтр|фильтр частиц]] над массивом карт и положений робота. Этот метод был предложен исследователями [[Университет Дьюка|университета Дьюка]] ([[Северная Каролина]]) в их публикации для Международной объединенной конференции по искусственному интеллекту ''IJCAI'' ({{lang-en|International Joint Conferences on Artificial Intelligence}}) в 2003 году<ref name=eliazar>{{Публикация| 1=Статья| автор=A. Eliazar, R. Parr| заглавие=DP-SLAM: Fast, Robust Simultaneous Localization and Mapping Without Predetermined Landmarks| ссылка=http://people.ee.duke.edu/~lcarin/Lihan4.21.06a.pdf| язык=en| издание=IJCAI| тип=proc| год=2003| месяц=| число=| том=| номер=| страницы=| issn=| архив дата=2017-07-06| архив=https://web.archive.org/web/20170706040111/http://people.ee.duke.edu/%7Elcarin/Lihan4.21.06a.pdf}}</ref>. Через год на Международной конференции по робототехнике и автоматизации ({{lang-en|IEEE International Conference on Robotics and Automation}}) ими была представлена модернизированная версия алгоритма ''DP-SLAM 2.0''<ref>{{Публикация| 1=Статья| автор=A. Eliazar, R. Parr| заглавие=DP-SLAM 2.0| ссылка=https://ieeexplore.ieee.org/abstract/document/1308006| язык=en| издание=IEEE International Conference on Robotics and Automation| тип=Proceedings| год=2004| месяц=| число=| том=| номер=| страницы=| doi=10.1109/ROBOT.2004.1308006| архив дата=2019-02-12| архив=https://web.archive.org/web/20190212070522/https://ieeexplore.ieee.org/abstract/document/1308006}}</ref>.

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

== Структурное представление карты ==
{{нет источников в разделе|дата=2019-02-10}}
Карта представляется в виде сетки с заполнением ячеек, занятых препятствиями.

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

== Оценка метода ==
Метод вызвал определённый интерес среди специалистов по [[прикладная математика|прикладной математике]] и [[робототехника|робототехнике]]. В ряде научных публикаций его эффективность — в сочетании с {{iw|Граф (тип данных)|обновляемыми графами|en|Graph (abstract data type)}} типа «[[генеалогическое древо]]» для представления оцифрованных карт местности — получила весьма высокие оценки<ref>{{публикация|книга
 | автор         = S. Thrun, J. Leonard
 | часть         = Simultaneous Localization and Mapping
 | ссылка часть  = 
 | заглавие      = Springer Handbook of Robotics
 | оригинал      = 
 | ссылка        = 
 | викитека      = 
 | ответственный = B. Siciliano, O. Khatib
 | издание       = 
 | место         = 
 | издательство  = Springer
 | год           = 2008
 | volume        = 
 | pages         = 883
 | columns       = 
 | allpages      = 
 | серия         = 
 | isbn          = 978-3-540-23957-4
 | doi           = 
 | тираж         = 
 | ref           = 
}}</ref>. В 2007 году, благодаря наличию в открытом доступе детальной документации и относительной простоте реализации, характеристики метода ''DP-SLAM'' стали объектом скрупулёзного сопоставления с некоторыми другими вариантами (''[[TEAMBOTICA]]'' и ''[[6D-SLAM]]'') общего алгоритма ''SLAM''<ref>{{Публикация | 1=Статья | автор=R.Ouellette, K. Hirasawa | заглавие=A comparison of SLAM implementations for indoor mobile robots | ссылка=https://ieeexplore.ieee.org/abstract/document/4399575 | язык=en | издание=IEEE/RSJ International Conference on Intelligent Robots and Systems | тип=Proceedings | год=2007 | месяц= | число= | том= | номер= | pages=1479—1484 | doi=10.1109/iros.2007.4399575 | архив дата=2019-02-12 | архив=https://web.archive.org/web/20190212011725/https://ieeexplore.ieee.org/abstract/document/4399575 }}</ref>. В 2010 году группа [[Франция|французских]] исследователей обратила внимание, что программное воплощение алгоритмической базы ''DP-SLAM'' потребует не более, чем 200 строк кода на языке программирования [[Си (язык программирования)|Си]]<ref>{{Публикация | 1= Статья | автор= B. Steux, O. Hamzaoui | заглавие= tinySLAM : a SLAM Algorithm in less than 200lines C-Language Program | ссылка= https://ieeexplore.ieee.org/abstract/document/5707402 | язык= en | издание= 11th International Conference on Control Automation Robotics & Vision | тип= Proceedings | год= 2010 | месяц=  | число=  | том=  | номер=  | pages= 1975—1979 | doi= 10.1109/ICARCV.2010.5707402 | архив дата= 2019-02-12 | архив= https://web.archive.org/web/20190212011749/https://ieeexplore.ieee.org/abstract/document/5707402 }}</ref>.

== Примечания ==
{{примечания}}

== Ссылки ==
* [https://users.cs.duke.edu/~parr/dpslam/ Официальный сайт проекта DP-SLAM]

[[Категория:Робототехника]]
[[Категория:Управление процессами]]