Перегляд вихідного коду сторінки SLAM (метод)

[[Файл:Stanley2.JPG|thumb|240px|Переможець змагань {{Нп|DARPA Grand Challenge|||}}&nbsp;— {{Нп|Stanley (автомобіль)|STANLEY||Stanley (vehicle)}}, використовував SLAM, як елемент своєї автономної системи водіння.]]
[[Файл:RoboCup Rescue arena map generated by robot Hector from Darmstadt at 2010 German open.jpg|thumb|Мапа створена SLAM-роботом.]]
При розв'язуванні задач навігації і картографії у [[Робототехніка|робототехніці]], '''одночасна локалізація і картографування''' ({{lang-en|simultaneous localization and mapping}}&nbsp;— '''SLAM''') є алгоритмічною обчислювальною задачею побудови і оновлення мапи невідомого оточення з одночасним відстежуванням місцеположення рухаючись по ньому. Хоча це схоже на [[Курка чи яйце?|задачу «курка чи яйце?»]], існує декілька алгоритмів, що розв'язують її, щонайменше приблизно, в скінченний час для певних умов. До популярних методів розв'язування належать {{Нп|фільтр часток|||Particle filter}}, [[розширений фільтр Калмана]] і GraphSLAM.

Алгоритми SLAM обмежуються наявними ресурсами, таким чином не можуть бути абсолютно досконалими, бо досягають оперативної доступності. Опубліковані методи і підходи реалізовані в [[Безпілотний автомобіль|безпілотних автомобілях]], [[Безпілотний літальний апарат|безпілотних літаючих засобах]], [[Автономний підводний апарат|автономних підводних апаратах]], [[Планетохід|планетоходах]], згодом виникли в [[Побутовий робот|побутових роботах]] і навіть всередині людського тіла.<ref name=Mountney2006>{{cite journal
 | author = Mountney, P.; Stoyanov, D.; Davison, A.; Yang, G-Z.
 | year = 2006
 | title = Simultaneous Stereoscope Localization and Soft-Tissue Mapping for Minimal Invasive Surgery
 | journal = MICCAI
 | volume = 1
 | pages = 347–354
 | url = http://www.sciweavers.org/external.php?u=http%3A%2F%2Fwww.doc.ic.ac.uk%2F%7Epmountne%2Fpublications%2FMICCAI%25202006.pdf&p=
 | accessdate = 2010-07-30
 | doi = 10.1007/11866565_43
 | archive-date = 12 січня 2017
 | archive-url = https://web.archive.org/web/20170112000819/http://www.sciweavers.org/external.php?u=http%3A%2F%2Fwww.doc.ic.ac.uk%2F%7Epmountne%2Fpublications%2FMICCAI%25202006.pdf&p=
 }}</ref>

== Постановка задачі ==

Дана послідовність даних спостереження сенсору <math>o_t</math> за дискретні проміжки часу <math>t</math>, задачею SLAM є розрахувати і визначити розташування агента <math>x_t</math> і мапу оточення <math>m_t.</math> Всі величини зазвичай ймовірнісні, тому необхідно обчислити:

: <math> P(m_t,x_t|o_{1:t}) </math>

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

: <math> 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. </math>

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

: <math> 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}). </math>

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

== Алгоритми ==
{{section-stub|дата=січень 2018}}
До статистичних методів, що використовуються для задач апроксимації наведених вище, належать: [[Фільтр Калмана|фільтр Калмана]], {{Нп|фільтр часток|||Particle filter}} (який є [[Метод Монте-Карло|методом Монте-Карло]]) і узгоджене сканування діапазонних даних. Вони дозволяють визначити оцінку функції апостеріорної ймовірності для позиції робота і параметрів мапи. {{Нп|Техніки оцінювання приналежності до множини|||Set estimation}} в основному засновуються на {{Нп|Поширення сталого інтервалу|поширенні сталого інтервалу||Interval propagation}}.<ref>{{cite journal|
last1=Jaulin|
first1=L.|
title=A nonlinear set-membership approach for the localization and map building of an underwater robot using interval constraint propagation|
journal=IEEE Transactions on Robotics|
year=2009|
url=http://www.ensta-bretagne.fr/jaulin/paper_reder_ieee_tro.pdf|
accessdate=3 жовтня 2016|
archive-date=5 жовтня 2016|
archive-url=https://web.archive.org/web/20161005222209/https://www.ensta-bretagne.fr/jaulin/paper_reder_ieee_tro.pdf}}</ref><ref>{{cite journal|
last1=Jaulin|
first1=L.|
title=Range-only SLAM with occupancy maps; A set-membership approach|
journal=IEEE Transactions on Robotics|
year=2011|
url=http://www.ensta-bretagne.fr/jaulin/paper_dig_slam.pdf|
accessdate=3 жовтня 2016|
archive-date=5 жовтня 2016|
archive-url=https://web.archive.org/web/20161005221906/https://www.ensta-bretagne.fr/jaulin/paper_dig_slam.pdf}}</ref>
Вони забезпечують множину, яка містить позицію робота і множину апроксимації мапи. [[Налаштування пучка]] є наступною популярною технікою у SLAM, який використовує дані зображень поєднані з оцінками розташування робота і орієнтирів на місцевості, тим самим підвищуючи точність мапи. Вона використовується в комерційних SLAM системах, таких як [https://www.google.com/atap/projecttango/ Проект Tango] {{Webarchive|url=https://web.archive.org/web/20140316165229/https://www.google.com/atap/projecttango/ |date=16 березня 2014 }} компанії Google.

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

=== Картографування ===

Побудова [[Топологічна мапа|топологічних мап]] це метод представлення довколишнього світу, який узагальнює структуру (тобто, [[Топологія|топологію]]) оточення замість створення геометрично точної мапи. Топологічні методи SLAM використовуються для підвищення загальної узгодженості метричних алгоритмів SLAM.<ref name=cummins2008>{{cite journal
|last1=Cummins
|first1=Mark
|last2=Newman
|first2=Paul
|title=FAB-MAP: Probabilistic localization and mapping in the space of appearance
|journal=The International Journal of Robotics Research
|date=June 2008
|volume=27
|issue=6
|pages=647–665
|doi=10.1177/0278364908090961
|url=http://www.robots.ox.ac.uk/~mjc/Papers/IJRR_2008_FabMap.pdf
|accessdate=23 липня 2014
|archive-date=12 травня 2014
|archive-url=https://web.archive.org/web/20140512085348/http://www.robots.ox.ac.uk/~mjc/Papers/IJRR_2008_FabMap.pdf
}}</ref>

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

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

=== Список методів SLAM ===

Список відомих реалізацій методів SLAM:
* EKF SLAM
* [[FastSLAM|FastSLAM 1.0]]
* [[FastSLAM|FastSLAM 2.0]]
* L-SLAM<ref name=Zikos2014>{{Citation
 | last = Zikos
 | first = Nikos
 | last2 = Petridis
 | first2 = Vassilios
 | title = 6-DoF Low Dimensionality SLAM (L-SLAM)
 | journal = Journal of Intelligent & Robotic Systems
 | pages = 1–18
 | publisher = Springer
 | doi = 10.1007/s10846-014-0029-6
 | year = 2014 
 | issn = 0921-0296}}</ref> [https://github.com/nzikos/L-SLAM (Код для Matlab)] {{Webarchive|url=https://web.archive.org/web/20180611032502/https://github.com/nzikos/L-SLAM |date=11 червня 2018 }}
* GraphSLAM
* Occupancy Grid SLAM<ref name=Trun2005>{{cite book 
 | author = Thrun, S. |author2=Burgard, W. |author3=Fox, D.
 | title = Probabilistic Robotics 
 | publisher = The MIT Press 
 | location = Cambridge 
 | year = 2005 
 | isbn = 0-262-20162-3 
}}</ref>
* [[DP-SLAM]]
* [http://www.robots.ox.ac.uk/~gk/PTAM Parallel Tracking and Mapping (PTAM)] {{Webarchive|url=https://web.archive.org/web/20161020152324/http://www.robots.ox.ac.uk/~gk/PTAM/ |date=20 жовтня 2016 }}<ref name=Klein07>{{cite journal
 | author = G. Klein and D. Murray
 | title = Parallel Tracking and Mapping for Small AR Workspaces
 | journal = International Symposium on Mixed and Augmented Reality (ISMAR)
 | url = http://www.robots.ox.ac.uk/~gk/publications/KleinMurray2007ISMAR.pdf
 | year = 2007
 | accessdate = 4 жовтня 2016
 | archive-date = 6 грудня 2016
 | archive-url = https://web.archive.org/web/20161206215928/http://robots.ox.ac.uk/%7Egk/publications/KleinMurray2007ISMAR.pdf/
 }}</ref>
* [https://vision.in.tum.de/lsdslam LSD-SLAM]<ref name=Engel14>{{cite journal
 | author = J. Engel and T. Schops and D. Cremers
 | title = LSD-SLAM: Large-Scale Direct Monocular SLAM
 | journal = European Conference on Computer Vision (ECCV)
 | url = https://vision.in.tum.de/_media/spezial/bib/engel14eccv.pdf
 | year = 2014
 | accessdate = 4 жовтня 2016
 | archive-date = 22 жовтня 2014
 | archive-url = https://web.archive.org/web/20141022190655/https://vision.in.tum.de/_media/spezial/bib/engel14eccv.pdf
 }}</ref> (доступно в відкритому коді)
* [http://webdiis.unizar.es/~raulmur/orbslam/ ORB-SLAM] {{Webarchive|url=https://web.archive.org/web/20160927211902/http://webdiis.unizar.es/~raulmur/orbslam/ |date=27 вересня 2016 }}<ref name=Mur-Artal15>{{cite journal
 | author = R. Mur-Artal and J. M. M. Montiel and J. D. Tardós
 | journal = IEEE Transactions on Robotics
 | title = ORB-SLAM: A Versatile and Accurate Monocular SLAM System
 | year = 2015
 | volume = 31
 | number = 5
 | pages=1147–1163
 | doi = 10.1109/TRO.2015.2463671
 | ISSN = 1552-3098
 | arxiv = 1502.00956}}</ref> (доступно в відкритому коді)
* ORB-SLAM2
* MonoSLAM
* [https://github.com/danping/CoSLAM CoSLAM] {{Webarchive|url=https://web.archive.org/web/20170406062151/https://github.com/danping/CoSLAM |date=6 квітня 2017 }}<ref name=Danping13>{{cite journal
 | author = D. Zou and P. Tan
 | title = CoSLAM: Collaborative Visual SLAM in Dynamic Environments
 | journal = IEEE Trans. on Pattern Analysis and Machine Intelligence
 | url = http://www.cs.sfu.ca/~pingtan/Papers/pami12_slam.pdf
 | publisher = IEEE
 | year = 2013
 | accessdate = 4 жовтня 2016
 | archive-date = 5 липня 2016
 | archive-url = https://web.archive.org/web/20160705111119/http://www.cs.sfu.ca/~pingtan/Papers/pami12_slam.pdf
 }} {{Webarchive|url=https://web.archive.org/web/20160705111119/http://www.cs.sfu.ca/~pingtan/Papers/pami12_slam.pdf |date= 5 липня 2016 }}</ref>
* [https://web.archive.org/web/20161011222338/http://openslam.org/openseqslam.html SeqSlam]<ref name=Milford>{{
cite journal
   |author = Michael J. Milford and Gordon. F. Wyeth
   |title = SeqSLAM: Visual Route-Based Navigation for Sunny Summer Days and Stormy Winter Nights
   |journal =  Proc. of Intl. Conf. on Robotics and Automation
}}
</ref>

== Див. також ==
* [[Структура із руху]]
* [[Реєстрація зображень]]
* [[Neato Robotics]]
* [[Комп'ютерне стереобачення]]
* {{Нп|Tango (platform)|||Tango (platform)}}
* {{Нп|Навігація і картографія у робототехніці|||Robotic mapping}}

== Примітки ==
{{reflist}}


{{Перекласти|en|дата=січень 2023}}


{{Робототехніка}}

[[Категорія:Обчислювальна геометрія]]
[[Категорія:Керування роботами]]
[[Категорія:Прикладне машинне навчання]]
[[Категорія:Рух у комп'ютернім зорі]]