Statement of problem of unknown environment recognizing, navigating and path planning by agent
An analytical review of the main world trends dominating in the framework of solving the problem of recognition of unknown environment, navigation and path planning by agent in it is given. The analysis of the structure of tasks that are the problem components shows that the direction of the propose...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2018
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/249 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-249 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/da/48ad72e040cee7ab30cd193d436c57da.pdf |
| spelling |
pp_isofts_kiev_ua-article-2492024-04-28T11:34:16Z Statement of problem of unknown environment recognizing, navigating and path planning by agent К постановке задачи распознавания неизвестной окружающей среды, навигации и планирования путей агентом в ней До постановки задачі розпізнавання невідомого оточуючого середовища, наві-гації та планування шляхів агентом в ньому Yalovets, A.L. agent; unknown environment; map; localization; path planning; trajectory; search graph UDC 004.94+004.896 агент; неизвестная окружающая среда; карта; локализация; планирование путей; траектория движения; граф поиска УДК 004.94+004.896 агент; невідоме оточуюче середовище; мапа; локалізація; планування шляхів; траєкторія руху; граф пошуку УДК 004.94+004.896 An analytical review of the main world trends dominating in the framework of solving the problem of recognition of unknown environment, navigation and path planning by agent in it is given. The analysis of the structure of tasks that are the problem components shows that the direction of the proposed researches belongs to the problem of simultaneous mapping and path planning. On the basis of the review, statement of problem for the case of single agent was proposed and a list of methods requiring priority development was determined.Problems in programming 2018; 1: 113-127 Приведен аналитический обзор основных тенденций, доминирующих в мире в рамках решения проблемы распознавания неизвестной окружающей среды, навигации и планирования путей агентом в ней. Проанализирована структура задач, являющихся составляющими этой проблемы, и установлено, что направление предлагаемых исследований принадлежит к проблематике одновременного построения карты и планирования пути. На основании обзора выполнена постановка задач исследований для случая одного агента и определен перечень методов, требующих первоочередной разработки.Problems in programming 2018; 1: 113-127 Наведено аналітичний огляд основних тенденцій, домінуючих в світі у рамках вирішення проблеми розпізнавання невідомого оточуючого середовища, навігації та планування шляхів агентом у ньому. Проаналізовано структуру задач, які є складовими цієї проблеми, та визначено, що напрям пропонованих досліджень належить до проблематики одночасної побудови мапи та планування шляху. На основі здійсненого огляду виконано постановку задач досліджень для випадку одного агента та визначено перелік методів, що потребують першочергової розробки.Problems in programming 2018; 1: 113-127 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2018-10-09 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/249 10.15407/pp2018.01.113 PROBLEMS IN PROGRAMMING; No 1 (2018); 113-127 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2018); 113-127 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2018); 113-127 1727-4907 10.15407/pp2018.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/249/245 Copyright (c) 2018 PROBLEMS OF PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T11:34:16Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
agent unknown environment map localization path planning trajectory search graph UDC 004.94+004.896 |
| spellingShingle |
agent unknown environment map localization path planning trajectory search graph UDC 004.94+004.896 Yalovets, A.L. Statement of problem of unknown environment recognizing, navigating and path planning by agent |
| topic_facet |
agent unknown environment map localization path planning trajectory search graph UDC 004.94+004.896 агент неизвестная окружающая среда карта локализация планирование путей траектория движения граф поиска УДК 004.94+004.896 агент невідоме оточуюче середовище мапа локалізація планування шляхів траєкторія руху граф пошуку УДК 004.94+004.896 |
| format |
Article |
| author |
Yalovets, A.L. |
| author_facet |
Yalovets, A.L. |
| author_sort |
Yalovets, A.L. |
| title |
Statement of problem of unknown environment recognizing, navigating and path planning by agent |
| title_short |
Statement of problem of unknown environment recognizing, navigating and path planning by agent |
| title_full |
Statement of problem of unknown environment recognizing, navigating and path planning by agent |
| title_fullStr |
Statement of problem of unknown environment recognizing, navigating and path planning by agent |
| title_full_unstemmed |
Statement of problem of unknown environment recognizing, navigating and path planning by agent |
| title_sort |
statement of problem of unknown environment recognizing, navigating and path planning by agent |
| title_alt |
К постановке задачи распознавания неизвестной окружающей среды, навигации и планирования путей агентом в ней До постановки задачі розпізнавання невідомого оточуючого середовища, наві-гації та планування шляхів агентом в ньому |
| description |
An analytical review of the main world trends dominating in the framework of solving the problem of recognition of unknown environment, navigation and path planning by agent in it is given. The analysis of the structure of tasks that are the problem components shows that the direction of the proposed researches belongs to the problem of simultaneous mapping and path planning. On the basis of the review, statement of problem for the case of single agent was proposed and a list of methods requiring priority development was determined.Problems in programming 2018; 1: 113-127 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/249 |
| work_keys_str_mv |
AT yalovetsal statementofproblemofunknownenvironmentrecognizingnavigatingandpathplanningbyagent AT yalovetsal kpostanovkezadačiraspoznavaniâneizvestnojokružaûŝejsredynavigaciiiplanirovaniâputejagentomvnej AT yalovetsal dopostanovkizadačírozpíznavannânevídomogootočuûčogoseredoviŝanavígacíítaplanuvannâšlâhívagentomvnʹomu |
| first_indexed |
2025-07-17T10:05:02Z |
| last_indexed |
2025-07-17T10:05:02Z |
| _version_ |
1850413084015853568 |
| fulltext |
Математичне моделювання об’єктів та процесів
© А.Л. Яловець, 2018
ISSN 1727-4907. Проблеми програмування. 2018. № 1 113
УДК 004.94+004.896
А.Л. Яловець
ДО ПОСТАНОВКИ ЗАДАЧІ РОЗПІЗНАВАННЯ НЕВІДОМОГО
ОТОЧУЮЧОГО СЕРЕДОВИЩА, НАВІГАЦІЇ ТА
ПЛАНУВАННЯ ШЛЯХІВ АГЕНТОМ В НЬОМУ
Наведено аналітичний огляд основних тенденцій, домінуючих в світі у рамках вирішення проблеми
розпізнавання невідомого оточуючого середовища, навігації та планування шляхів агентом у ньому.
Проаналізовано структуру задач, які є складовими цієї проблеми, та визначено, що напрям пропонова-
них досліджень належить до проблематики одночасної побудови мапи та планування шляху. На основі
здійсненого огляду виконано постановку задач досліджень для випадку одного агента та визначено пе-
релік методів, що потребують першочергової розробки.
Ключові слова: агент, невідоме оточуюче середовище, мапа, локалізація, планування шляхів, траєкторія
руху, граф пошуку.
Вступ
Проблема планування дій мобільно-
го агента (прототипу мобільного робота) в
невідомому оточуючому середовищі на
сьогоднішній день є однією з найбільш
складних та актуальних задач у галузі
штучного інтелекту: очікується, що її ви-
рішення створить умови для потужного
розвитку та удосконалення відповідних
технологій робототехніки. Відомо, що мо-
більні роботи можуть бути застосовані не
тільки для вирішення побутових завдань
(наприклад, для автоматичного прибиран-
ня приміщень (пилосос)), а й для виконан-
ня спеціальних завдань (у тому числі по-
шуково-рятувальних та розвідувальних
дій) у невідомому та небезпечному оточу-
ючому середовищі. Водночас, реальне ви-
користання мобільних роботів для відпра-
цювання відповідних методів пов’язано з
певними ускладненнями і в загальному
випадку є неефективним: по-перше – це
коштовний та трудомісткий процес; по-
друге, на практиці таке використання від-
бувається в конкретних фіксованих умовах
оточуючого середовища, що не дозволяє
гарантувати робастність відповідних мето-
дів у будь-якій ситуації для довільного
оточуючого середовища.
На відміну від цього, використання
мультиагентного підходу для вирішення
означених задач дозволяє перевірити ме-
тоди моделювання поведінки агентів у
будь-яких ситуаціях для множини оточую-
чих середовищ з різними властивостями.
Тому далі ми будемо вживати поняття
«агент», розуміючи під ним прототип мо-
більного робота.
Вирішення досліджуваної проблеми
для випадку одного агента передбачає
розв’язання трьох взаємопов’язаних задач
його навігації: побудови мапи (mapping),
локалізації (localization) та планування
шляху (path planning). Побудова мапи – це
проблема інтеграції інформації, що надхо-
дить з сенсорів агента, зібраної з різних
місць його розташування в оточуючому
середовищі. Коректна обробка даних сен-
сорів і точна локалізація є фундаменталь-
ними для забезпечення адекватності ство-
рюваної мапи. Локалізація – це проблема
оцінювання фактичного місцезнаходження
агента, виходячи з показників сенсорів та
відомостей з вже побудованої мапи. Точна
мапа та надійні сенсори мають вирішальне
значення для визначення правильної лока-
лізації. Планування шляху або проблема
керування рухом – це проблема створення
допустимої та безпечної (що унеможлив-
лює зіткнення з будь-якими зустрічними
об’єктами) траєкторії руху від поточного
місцезнаходження агента до цілі, де ство-
рювана траєкторія має враховувати обме-
ження, що містяться на вже існуючій мапі.
При цьому важливе значення мають точ-
ність побудови мапи та надійність визна-
чення локалізації.
На рис. 1 показано три зазначені за-
дачі та їх перетини, що формують основні
Математичне моделювання об’єктів та процесів
114
сучасні напрями досліджень у рамках ви-
рішення аналізованої проблеми.
Так, перетин задач побудови мапи
та локалізації утворив напрям досліджень з
одночасної локалізації та побудови мапи
(simultaneous localization and mapping
(SLAM)). Ці задачі є взаємопов’язаними та
взаємозалежними і тому SLAM часто на-
зивають проблемою «куриці» та «яйця»:
для рішення задач локалізації потрібна то-
чна мапа, тоді як для побудови мапи пот-
рібна точна оцінка місцезнаходження аге-
нта. Основні аспекти сучасного стану дос-
ліджень у галузі SLAM викладено в [3, 4].
Активна локалізація спрямована на
те, щоб спланувати дії агента щодо знахо-
дження такого місця на мапі, яке дозво-
лить покращити оцінку його місцезнахо-
дження. Зазначимо, що більшість існую-
чих підходів до локалізації є пасивними,
тобто орієнтованими на оцінку місцезна-
ходження агента виключно на основі да-
них, що надходять від сенсорів. Активна
локалізація додатково передбачає, що про-
цедура локалізації має частковий або пов-
ний контроль над діями агента, надаючи
можливість покращити ефективність та
надійність локалізації. При цьому ключо-
вими проблемами є вирішення питань «ку-
ди рухатись» та «де шукати», щоб най-
кращим чином визначити місцезнахо-
дження агента.
В свою чергу, перетин задач побу-
дови мапи та планування руху утворює
наш напрям досліджень. Відомі підходи у
цьому напряму досліджень передбачають
наявність точної інформації про місцезна-
ходження агента та спрямовані на вирі-
шення задач ефективного керування його
рухом через навколишнє середовище з ме-
тою побудови мапи. Ці підходи, як прави-
ло, використовують такі подання мапи як
подання, засновані на орієнтирах та по-
дання графу огляду (див. п. 2 статті), і за-
дача планування шляхів відповідає задачі
локального пошуку шляху. В нашому ви-
падку теж передбачається наявність точної
інформації про місцезнаходження агента,
але, на відміну від відомих підходів, ми
плануємо вирішувати проблему побудови
мапи шляхом розпізнавання і класифікації
агентом об’єктів оточуючого середовища в
процесі його руху через оточуюче середо-
вище з метою одночасного плануванням
агентом свого подальшого шляху за допо-
могою методів локального пошуку. Якщо
відомі підходи можна узагальнено назвати
як підходи з одночасного планування шляху
та побудови мапи (simultaneous planning
and mapping (SPAM)), то наш напрям дос-
ліджень – підходом з одночасної побудови
мапи та планування шляху (simultaneous
mapping and planning (SMAP)).
Рис.1. Галузі досліджень проблеми навігації агентів (адаптовано з [1, 2])
Математичне моделювання об’єктів та процесів
115
Зазначимо також, що підходи з по-
дання мапи, що включають подання, за-
сновані на зайнятості, геометричні подан-
ня та подання графа маршруту (див. п. 2
статті), орієнтовані на використання гло-
бальних методів пошуку на дискретному
поданні (у вигляді дорожньої мапи, подан-
ні, заснованому на клітковій декомпозиції
тощо) вільного простору оточуючого сере-
довища агента. Тобто такі підходи перед-
бачають існування мапи оточуючого сере-
довища та перетворення її у відповідне
дискретне подання перед виконанням по-
шуку шляхів і використовуються, зокрема,
в рамках напряму досліджень з планування
шляху/керування рухом (див. рис. 1).
Перетин всіх трьох задач утворює
напрям досліджень, що відповідає так зва-
ним інтегрованим підходам, які одночасно
торкаються розв’язування проблем побу-
дови мапи, локалізації та планування шля-
ху. Інтегровані підходи також називаються
підходами з рішення проблеми одночасно-
го планування, локалізації та побудови ма-
пи (simultaneous planning, localization, and
mapping (SPLAM)). Рішення проблеми
SPLAM дозволяє агенту отримувати дані
датчиків, автономно рухаючись через своє
оточуюче середовище, та одночасно буду-
вати мапу. В кожний момент часу свого
руху агент обирає дії, спрямовані на по-
ліпшення своєї локалізації, отримує інфо-
рмацію про фрагменти невідомого оточу-
ючого середовища та поліпшує модель
своєї мапи шляхом їх обробки. Нарешті
передбачається, що він має створити точну
модель всього оточуючого середовища, а
також визначити своє місцезнаходження в
межах цієї моделі.
На сьогоднішній день світові дос-
лідження охоплюють всі названі напрями.
При цьому аналізуються різні аспекти
проблеми, для чого досліджується поведі-
нка як одного агента, так і групи агентів.
Зважаючи на складність аналізованої про-
блеми, використання для її вирішення
групи агентів (у порівнянні з використан-
ням одного агента) має як свої переваги,
так і недоліки. До переваг, зокрема, нале-
жать наступні: агенти, що кооперуються,
спроможні швидше вирішити відповідні
задачі (наприклад, побудову загальної
мапи, знаходження шуканих об’єктів то-
що), ніж один агент; у групи агентів бі-
льша імовірність успішно завершити ви-
рішення покладених на них завдань, ніж у
одного агента, оскільки відмова окремого
агента групи не унеможливлює отримання
загального кінцевого результату. Одним з
основних недоліків, що може негативно
вплинути на ефективність вирішення за-
дач, є наступний: в процесі руху агентів,
що належать групі, можливі ситуації їх
зустрічей, внаслідок чого вони мають ви-
рішувати задачі уникнення зіткнень шля-
хом затримок або об’їздів таких переш-
код, що збільшує час вирішення загальної
задачі. Тобто на відміну від ситуації з од-
ним агентом, коли, наприклад, його ото-
чуюче середовище є статичним, у випадку
розгляду групи агентів це оточуюче сере-
довище стає динамічним за рахунок ди-
намічної зміни станів агентів, що входять
до складу групи.
Зазначимо, що в наших дослі-
дженнях планується вирішувати проблему
SMAP за допомогою групи агентів, які
мають координувати свої дії та кооперува-
тися між собою для вирішення загальної
задачі.
1. Сутність проблеми локалізації
Вирішення проблеми локалізації
знаходиться в безпосередньому зв’язку з
наступними аспектами її розгляду [5]:
1) ступінь інформованості агента
щодо його поточного розташування;
2) тип оточуючого середовища, в
якому діє агент;
3) ступінь контролю за рухом
агента з боку процедури локалізації;
4) кількість агентів, що одночасно
діють в оточуючому середовищі.
Коротко охарактеризуємо сутність
проблеми локалізації з точки зору кожного
із зазначених аспектів.
Ступінь інформованості агента що-
до його поточного розташування залежить
від точності та повноти інформації, якою
він оперує у процесі руху. Розрізняють три
можливі ситуації:
● локальна локалізація (local
localization) або відстеження місцезнахо-
Математичне моделювання об’єктів та процесів
116
дження (position tracking) характеризується
тим, що агент відстежує своє місцезнахо-
дження у кожний момент часу, виходячи з
відомих координат його розташування на
початку руху. Вважається, що в агента по-
хибки оцінки переміщення (одометрія) та
кутів поворотів незначні. Це найпростіша
ситуація щодо вирішення проблеми лока-
лізації;
● глобальна локалізація (global
localization) характеризується тим, що аге-
нту невідомі координати його розташуван-
ня на початку руху, і він має відстежувати
своє поточне місцезнаходження, перебу-
ваючи в межах оточуючого середовища,
але не знаючи, де саме він знаходиться. Ця
ситуація складніша, ніж попередня;
● проблема «викрадення» (kid-
napped problem) агента, яка є найбільш
складним випадком глобальної локалізації.
Сутність проблеми полягає у тому, що
агент був без його відома переміщений в
інше місце, але він впевнений при цьому,
що своє поточне місцезнаходження визна-
чає коректно. Вирішення цієї проблеми
(забезпечення коректного визначення міс-
цезнаходження) націлене на підвищення
спроможності агента відновлюватись після
помилок глобальної локалізації.
Тип оточуючого середовища, в
якому діє агент, також може впливати на
коректність вирішення проблеми локаліза-
ції. Оточуюче середовище є статичним,
якщо в ньому рухається лише один агент, а
інші об’єкти не змінюють свого геометри-
чного розташування. На відміну від цього,
в динамічному оточуючому середовищі
можуть рухатись й інші об’єкти, розташу-
вання яких може постійно змінюватись,
тим самим впливаючи на коректність ви-
рішення проблеми локалізації.
За ступенем контролю за рухом
агента з боку процедури локалізації розрі-
зняють випадки пасивної та активної лока-
лізації (див. рис. 1). У випадку пасивної
локалізації визначення місцезнаходження
агента відбувається тільки на основі пока-
зників сенсорів. У випадку активної лока-
лізації відповідні процедури керують ру-
хом агента з метою мінімізації помилок
локалізації.
В залежності від кількості агентів,
що одночасно діють в оточуючому середо-
вищі, проблема локалізації вирішується
або для одного агента, або для множини
агентів. У першому випадку проблема ло-
калізації стосується тільки одного агента і
не ускладнена необхідністю одночасного
вирішення проблеми комунікації з іншими
агентами. У другому випадку агенти по-
винні кооперуватися між собою з метою
побудови загальної мапи, і некоректне ви-
рішення проблеми локалізації може суттє-
во вплинути на якість створення такої ма-
пи, оскільки одні і ті ж самі об’єкти мо-
жуть мати різні координати на мапі вна-
слідок похибок вимірювання, отриманих
різними агентами.
Для вирішення проблеми локаліза-
ції використовуються різні підходи, в тому
числі й імовірнісні, які ґрунтуються на ви-
користанні фільтрів Байєса (зокрема, алго-
ритм локалізації Маркова, алгоритм лока-
лізації Монте Карло, алгоритм фільтру Ка-
лмана та його модифікації тощо). Детально
різні аспекти проблеми локалізації викла-
дено в [5, 6].
2. Огляд відомих підходів до
побудови та подання мапи
оточуючого середовища
Побудова агентом мапи оточуючого
середовища – це складна науково-практич-
на проблема, вирішення якої передбачає
спроможність агента, починаючи з деякої
початкової точки його розташування, ав-
тономно дослідити оточуюче середовище
за допомогою своїх сенсорів, та отримати
й інтерпретувати відповідні дані, на основі
яких створити власну мапу та локалізувати
себе відносно її. При побудові мапи вико-
ристовуються відповідні підходи з її по-
дання.
На рис. 2 на верхньому рівні таксо-
номії класифікацію підходів виконано ви-
ходячи з розбіжностей у поданні просто-
рових відношень між основними сутнос-
тями мапи, що дозволило виділити два ос-
новних класи таксономії: подання, засно-
вані на координатах (або метричні подан-
ня) та реляційні подання (які, зокрема,
Математичне моделювання об’єктів та процесів
117
Рис. 2. Таксономія існуючих підходів з подання мапи (адаптовано з [7])
включають топологічні мапи). Розбіжності
між цими поданнями полягають у наступ-
ному:
― подання, засновані на коорди-
натах, неявно відображають просторові
відношення між основними сутностями,
надаючи координати для кожного з прос-
торових об’єктів у рамках єдиної глобаль-
ної системи координат;
― реляційні подання виражають
просторові відношення між основними
сутностями, явно визначаючи, що існує
відповідне відношення між відповідним
набором об’єктів.
Подання, засновані на координа-
тах, поділяються на три підкласи: подан-
ня, засновані на зайнятості; геометричні
подання та подання, засновані на орієн-
тирах.
Подання, засновані на зайнятості
(Occupancy-based representations) орієнто-
вані на визначення зайнятих та вільних ча-
стин простору шляхом його розбиття на
зайняті та вільні клітинки. Як правило, ро-
збиття не залежить від розподілу об’єктів у
просторі та є рівномірним в тому сенсі, що
всі клітинки мають однакову форму і роз-
мір. При цьому в більшості випадків вико-
ристовується так звана мережа зайнятості
(occupancy grid), в якій подається невизна-
ченість щодо стану зайнятості кожної клі-
тинки як значення правдоподібності
]1,0[l . Переваги використання мереж
зайнятості полягають у легкості злиття та
гнучкості при об’єднанні даних, отрима-
них агентом з різних типів сенсорів. Недо-
ліки їх використання полягають у значних
обчислювальних витратах при обробці ве-
ликих мереж зайнятості та труднощах у
знаходженні оптимальних шляхів на мапі
без залучення людини.
Геометричні подання (Geometric
representations) використовують множину
геометричних примітивів (точки, лінії,
криві тощо) для опису множини перешкод
як границь вільного простору, розташова-
них в єдиній системі координат. Геомет-
ричні подання дозволяють якісно подавати
довільні середовища за умови використан-
ня геометричних примітивів, які забезпе-
чують коректну апроксимацію форм гра-
ниць об’єкта (наприклад, точок, ліній, по-
ліліній). Таке подання, як правило, є ком-
пактним. Але при цьому існує проблема
злиття даних для об’єднання відповідних
об’єктів на мапі, яка залишається однією з
найбільш складних проблем у рамках гео-
метричного подання. Оскільки геометрич-
ні подання описують границі вільного
простору середовища, вони, з одного боку,
добре підходять для вирішення задач ло-
калізації, з іншого, – для планування шля-
хів. Водночас планування шляхів вимагає
створення дискретного простору пошуку в
межах середовища для використання відо-
мих методів пошуку, що призводить до
додаткових обчислювальних витрат. Типо-
вими підходами для вирішення таких задач
є підходи дорожньої мапи (roadmap), кліт-
кової декомпозиції (cell decomposition) то-
що. До недоліків геометричного подання
можна віднести необхідність постійного
відстеження, які частини оточуючого се-
редовища вже оглянуті та потребують яв-
ного подання і постійного поновлення
опису оглянутої області.
Подання, засновані на орієнтирах
(Landmark-based representations) подають
Математичне моделювання об’єктів та процесів
118
оточуюче середовище як набір важливих
об’єктів (орієнтирів), видобутих з даних
сенсорів, де позиції орієнтирів визнача-
ються у глобальній системі координат. Ге-
ометричні подання та подання, засновані
на орієнтирах, належать до подання, засно-
ваного на характеристиках (feature-based
representations), оскільки ці підходи збіга-
ються за ознакою подібності структур да-
них про об’єкти оточуючого середовища
та використовуваних методів обробки не-
визначеності. Однак між цими поданнями
існують розбіжності з точки зору просто-
рового подання даних про об’єкти оточу-
ючого середовища: якщо геометричні по-
дання повністю моделюють границі віль-
ного простору, то подання, засновані на
орієнтирах, орієнтовані на конкретні
об’єкти, корисні для вирішення задач ло-
калізації та орієнтації у просторі. Подання,
засновані на орієнтирах, є доволі компакт-
ними (в залежності від щільності орієнти-
рів в оточуючому середовищі) і достатньо
добре підходять для опису великих сере-
довищ. Ці подання широко використову-
ються в підходах SLAM, оскільки дозво-
ляють виконувати імовірнісну обробку не-
визначеностей. Однак використання по-
дання, заснованого на орієнтирах, не має
універсальності, властивої для подання,
заснованого на зайнятості, та геометрич-
ного подання, і обмежується тільки сере-
довищами, в яких наявні орієнтири доста-
тньої щільності.
Реляційні подання явно визнача-
ють відношення, що існують між
об’єктами оточуючого середовища. Біль-
шість сучасних реляційних подань явля-
ють собою графові подання, в яких вузли
позначають базові сутності (наприклад,
види, місця, об’єкти), а ребра подають від-
повідні просторові відношення (напри-
клад, суміжність або зв’язок). Такі подання
часто називають топологічними мапами. В
таксономії (див. рис. 2) розрізняються два
види подань реляційних графів: подання
графа огляду та подання графа маршруту.
В поданнях графа огляду вузли явно не
подані в оточуючому середовищі, а утво-
рюються в результаті його розпізнавання
агентом: кожному вузлу відповідає вид,
доступний для огляду з відповідної позиції
розташування агента. Виконання розподі-
лу вузлів у вільному просторі середовища
засновано на досягненні достатньої різниці
між видами, отримуваними агентом з сусі-
дніх вузлів. На відміну від цього, в подан-
нях графу маршруту вузли явно подані в
оточуючому середовищі: граф маршруту
подає середовище як мережу різних марш-
рутів, а вузли позначають визначні місця
та особливі орієнтири, що розташовані
вздовж маршруту. Часто подання графа
маршруту безпосередньо відображає топо-
логію вільного простору.
Подання графа огляду (View graph
representations) характеризуються тим, що
в таких графах вузли безпосередньо асоці-
йовані з конкретною вхідною інформацією
сенсора, що називається видом (view),
отримуваною агентом з деякого місця його
розташування. Зв’язок між двома вузлами
враховує той факт, що обидва види були
отримані в послідовному порядку і, як на-
слідок, наявна просторова суміжність від-
повідних місцеположень. Отже, зв’язок
надає інформацію, необхідну для перемі-
щення агента між цими місцезнаходжен-
нями. Вузли мають розподілятися достат-
ньо щільно для досягнення надійного пе-
реміщення між ними на основі навігацій-
них можливостей агента. Таким чином,
побудова графа огляду відповідає ство-
ренню мережі вузлів, яка охоплює все ото-
чуюче середовище. Водночас, хоча графи
огляду надають інформацію для здійснен-
ня успішної навігації, отримувані при цьо-
му шляхи руху агента, як правило, не є оп-
тимальними. Основним недоліком подання
графа огляду є те, що воно не надає струк-
турованої інформації про оточуюче сере-
довище.
Подання графа маршруту (Route
graph representations) характеризуються
тим, що в таких графах вузли позначають
визначні місця, що існують у середовищі, а
ребра відображають шляхи, що зв’язують
такі місця, та дозволяють агенту перемі-
щуватись з одного місця в інше. У бага-
тьох підходах граф маршруту формується
з геометрії середовища шляхом перетво-
рення вільного простору на набір одномір-
них кривих, що називається дорожньою
мапою (roadmap). Для цього, зокрема, ви-
Математичне моделювання об’єктів та процесів
119
користовується діаграма Вороного та її
модифікації. Подання графа маршруту до-
зволяє ефективно вирішувати задачі пла-
нування шляху: структура графа відпові-
дає графу простору пошуку, на якому мо-
жна шукати шляхи за допомогою відомих
методів пошуку на графах (зокрема, алго-
ритму Дейкстри, А* тощо). Однією з пере-
ваг подання графа маршруту є те, що воно
полегшує систематичне дослідження ото-
чуючого середовища: для того, щоби охо-
пити все середовище, достатньо відстежи-
ти всі ребра графа. Іншою перевагою цього
подання є його компактність, що створює
необхідні умови для спрощення вирішення
задач комунікації агентів та обміну між
ними інформацією, необхідною для побу-
дови загальної мапи групою агентів. Вод-
ночас, проблема локалізації є достатньо
складною проблемою для подання графа
маршруту.
3. Огляд відомих методів
формування та планування
шляхів агентом
3.1. Огляд основних підходів до
формування шляхів. Подання мапи, опи-
сані в п. 2 статті, використовуються аген-
том для вирішення задач планування шля-
хів в оточуючому середовищі. В більшості
випадків для вирішення таких задач агент
має перетворити існуючу модель оточую-
чого середовища (мапу) в деяке дискретне
подання, придатне для здійснення плану-
вання шляхів за допомогою відомих мето-
дів пошуку. При цьому використовуються
наступні підходи [6, 8]:
― планування на основі потенцій-
них полів (Potential field planning). Цей під-
хід засновується на створенні поля або
градієнту на мапі агента, що направляє
агента у вільному просторі оточуючого
середовища до цільової позиції з множини
його попередніх позицій;
― побудова графа пошуку (Graph
search). Цей підхід передбачає побудову
графа зв’язності у вільному просторі ото-
чуючого середовища, на якому і здійсню-
ється пошук шляхів. Процес побудови
графа пошуку часто виконується в автоно-
мному (офф-лайн) режимі.
Планування на основі потенцій-
них полів засновується на ідеї створення
штучного потенційного поля в оточуючо-
му середовищі агента, де агент розгляда-
ється як точка, на яку впливає це поле.
Ціль (глобальний мінімум у цьому полі)
діє на агента як сила тяжіння, а перешко-
ди – як сили відштовхування. Суперпози-
ція всіх сил плавно направляє агента до
цілі, одночасно уникаючи його зіткнень з
відомими перешкодами. Треба зауважити,
що використання підходу потенційних
полів дозволяє забезпечити більше, ніж
планування шляху. Таке поле утворює за-
кон керування рухом агента: якщо агент
може локалізувати своє місцезнаходження
відносно мапи та потенційного поля, то
він завжди може визначити свій наступ-
ний потрібний крок, заснований на полі.
Основним недоліком підходу на основі
потенційних полів є те, що у полі можуть
існувати локальні мінімуми, які можуть
дезорієнтувати агента у пошуку цілі.
Побудова графа пошуку лежить в
основі створення дорожньої мапи та вико-
ристовується в рамках кліткової декомпо-
зиції.
При створенні дорожньої мапи
агент з’єднує початкову та цільову позиції
у вільному просторі оточуючого середо-
вища множиною ліній, що утворюють
граф зв’язності як множину шляхів, що
існують між початковою та цільовою по-
зиціями. Для створення дорожньої мапи
найбільше поширення отримали підходи з
побудови графа видимості (visibility graph)
та діаграми Вороного (Voronoi diagram).
Граф видимості складається з мно-
жини ребер, що зв’язують всі пари вер-
шин, що є видимими (тобто ребра прохо-
дять через вільний простір оточуючого се-
редовища) між собою (включаючи почат-
кову та цільові позиції як вершини). Прямі
лінії (шляхи), що з’єднують ці вершини, є
найкоротшими відстанями між ними і за-
дача пошуку на утворюваному графу ви-
димості полягає у знаходженні за допомо-
гою методів пошуку на графах найкорот-
шого шляху з множини шляхів, існуючих
між початковою та цільовою вершинами
цього графа. Завдяки досить простій про-
цедурі його побудови, граф видимості от-
Математичне моделювання об’єктів та процесів
120
римав досить широке використання на
практиці. Водночас, таке подання дорож-
ньої мапи має свої недоліки. По-перше,
розмір графу видимості зростає із збіль-
шенням полігонів перешкод, що негативно
впливає на ефективність використовува-
них процедур пошуку на цьому графі. По-
друге, ребра, що утворюються при побудо-
ві графа видимості, проходять на мініма-
льній відстані від перешкод, що негативно
впливає на безпечність навігації агента по
обраному найкоротшому шляху.
На відміну від графа видимості, при
побудові діаграми Вороного забезпечуєть-
ся максимізація відстані між агентом та
перешкодами на мапі. При побудові діаг-
рами Вороного знаходиться множина то-
чок, кожна з яких є центром круга, вписа-
ного у вільний простір оточуючого сере-
довища, який торкається як мінімум двох
точок контурів перешкод. При з’єднанні
послідовностей таких точок утворюються
ребра, які складаються з прямих та пара-
болічних сегментів, а вершини графа від-
повідають точкам зустрічі різних ребер та
початковій і цільовій вершинам. На відмі-
ну від шляху, знайденого на графі видимо-
сті, найкоротший шлях, знайдений на діаг-
рамі Вороного, не є оптимальним за кри-
терієм довжини шляху.
Основна ідея кліткової декомпози-
ції полягає у розподілі оточуючого середо-
вища на геометричні області (клітинки)
двох категорій: вільні клітинки та зайняті
клітинки. Розрізняють два види кліткової
декомпозиції: точну та приблизну.
При точній клітковій декомпозиції
створювані клітинки є або повністю віль-
ними, або повністю зайнятими. При цьому
об’єднання всіх вільних клітинок у точно-
сті дорівнює вільному простору оточуючо-
го середовища. Для забезпечення пошуку
шляхів на множині вільних клітинок буду-
ється граф суміжності, у якого ребрами є
шляхи, що існують між суміжними клітин-
ками, а вершинами графа є такі клітинки.
Пошук шляху на графі полягає у знахо-
дженні послідовності суміжних клітинок,
через які проходить шлях з початкової по-
зиції у цільову. Основним недоліком точ-
ної кліткової декомпозиції є те, що кіль-
кість клітинок і, як наслідок, загальна ефе-
ктивність планування шляхів залежить від
щільності та складності об’єктів оточую-
чого середовища.
При приблизній клітковій декомпо-
зиції, на відміну від точної кліткової деко-
мпозиції, клітинки мають наперед визна-
чену форму (наприклад, форму прямокут-
ника). Якщо в процесі розбиття з’ясову-
ється, що отримана клітинка є повністю
вільною, то вона далі не декомпозується. В
супротивному випадку виконується пода-
льша декомпозиція такої клітинки на мен-
ші клітинки такої ж форми. Побудова гра-
фа зв’язності, який проходить тільки через
повністю вільні клітинки, виконується за
аналогією з побудовою графа суміжності у
випадку точної кліткової декомпозиції.
Пошук шляху на такому графі завершуєть-
ся успішно, якщо існує шлях між початко-
вою та цільовою позиціями. Неуспішний
результат може означати або відсутність
такого шляху, або недостатність виконаної
декомпозиції. Таким чином, в рамках при-
близної кліткової декомпозиції пошук
шляхів може виконуватись ієрархічно
шляхом поступової деталізації ступені де-
композиції. В наслідок цього приблизна
кліткова декомпозиція є однією з найбільш
популярних технік з побудови графа по-
шуку.
3.2. Огляд найбільш відомих ме-
тодів планування шляхів. Для пошуку
шляхів на графах, створюваних за допомо-
гою підходів, описаних в п. 3.1, викорис-
товуються різні методи (алгоритми), в то-
му числі [8 – 10]: пошуку в ширину, пошу-
ку в глибину, Дейкстри, А*, D*.
Метод пошуку в ширину лежить в
основі алгоритму обходу графа, який по-
чинає свою роботу з кореневої вершини
графа, «розкриваючи» її, та відвідує всі її
суміжні вершини, послідовно «розкриваю-
чи» кожну з них і так далі. Таким чином,
при пошуку в ширину перед «розкриттям»
будь-яких вершин наступного рівня відбу-
вається «розкриття» всіх вершин поперед-
нього рівня графа. Алгоритм пошуку заве-
ршує свою роботу тоді, коли буде знайде-
на цільова вершина. Зазначимо, що алго-
ритм пошуку в ширину завжди формує
шлях з мінімальною кількістю ребер між
кореневою та цільовою вершинами. Недо-
Математичне моделювання об’єктів та процесів
121
ліком методу пошуку в ширину є велика
потреба у пам’яті, необхідної для збере-
ження оброблюваних даних: цей метод по-
требує збереження всіх відвіданих вершин.
Метод пошуку в глибину лежить в
основі алгоритму обходу графа, який по-
чинає свою роботу з деякої кореневої вер-
шини (таких вершин може бути декілька) і
намагається йти «в глиб» графа наскільки
це можливо. При виконанні алгоритму до-
сліджуються всі ребра, що виходять з і-ої
вершини, «розкритої» останньою, і зали-
шає вершину тільки тоді, коли не залиши-
лось недосліджених ребер, при цьому від-
бувається повернення до вершини, з якої
була «розкрита» і-та вершина. Процес об-
ходу графа триватиме до тих пір, доки не
будуть «розкриті» всі вершини, досяжні з
оброблюваної кореневої вершини. Якщо
при цьому залишаються «нерозкриті» ве-
ршини (наприклад, інші кореневі верши-
ни), то одна з них обирається як нова поча-
ткова вершина і процес обходу графа по-
вторюється вже відносно неї. Алгоритм
пошуку, як і у випадку пошуку в ширину,
завершує свою роботу тоді, коли буде
знайдена цільова вершина. Недоліком ме-
тоду пошуку в глибину є те, що він може
повторно «розкрити» раніше відвідані ве-
ршини та створити зайві шляхи, хоча ці
недоліки можуть бути легко усунені при
програмній реалізації алгоритму. Перева-
гою цього методу є невелика потреба у
пам’яті, необхідної для збереження оброб-
люваних даних: цей метод потребує збе-
реження тільки єдиного шляху від корене-
вої вершини до термінальної наряду з усі-
ма «нерозкритими» суміжними вершинами
для кожної вершини цього шляху.
Алгоритм Дейкстри подібний за
принципом обходу графа методу пошуку в
ширину за винятком того, що він здійснює
пошук найкоротшого шляху з початкової
до цільової вершини на зваженому графі, в
якому ваги ребер невід’ємні. Алгоритм
Дейкстри знаходить найкоротші шляхи до
вершин графа в порядку їх віддалення від
початкової вершини. На кожному кроці
ітерації алгоритм визначає найкоротші
шляхи з можливих альтернатив завдяки
знаходженню шляхів з мінімальною сума-
рною вагою ребер. В загальному випадку
перед початком і-ої ітерації алгоритм ви-
значає найкоротші шляхи до і–1 інших ве-
ршин, найближчих до початкової. Ці вер-
шини, початкова вершина та ребра найко-
ротших шляхів, що ведуть до цих вершин з
початкової вершини, утворюють підграф
даного графа. Вершина, найближча до по-
чаткової, може бути знайдена серед вер-
шин, суміжних кінцевій вершині цього
підграфа. Для визначення і-ої найближчої
вершини алгоритм обчислює для кожної
суміжної вершини суму ваги ребра, що
з’єднує таку вершину з найближчою вер-
шиною підграфа, та мінімальної сумарної
ваги ребер (раніше визначеної алгорит-
мом), що ведуть від початкової вершини
до цієї найближчої вершини підграфа, і
далі обирає вершину з мінімальною су-
мою. Алгоритм завершує свою роботу то-
ді, коли будуть досліджені всі шляхи, що
ведуть від початкової до цільової вершини,
та визначено найкоротший шлях як шлях з
мінімальною сумарною вагою утворюю-
чих його ребер.
Алгоритм А* є удосконаленням ал-
горитму Дейкстри за рахунок введення ев-
ристичної функції, що враховує властивос-
ті графа пошуку і дозволяє зменшити кіль-
кість досліджуваних вершин графа. В ал-
горитмі А* порядок обходу вершин графа
визначається евристичною функцією )(nf
як сумою функції )(ng вартості шляху від
початкової до даної вершини n та функції
)(nh як евристичної оцінки вартості шляху
від цієї вершини n до цільової:
)()()( nhngnf . Алгоритм А* досліджує
граф ітеративно, розглядаючи шляхи, що
виходять з початкової вершини. На кож-
ному кроці ітерації алгоритм розглядає ве-
ршини, суміжні поточній вершині, та оби-
рає ту з них, для якої )(nf є мінімальною,
після чого ця вершина «розкривається». В
загальному випадку на кожному кроці іте-
рації алгоритм оперує з множиною шляхів
від початкової вершини до ще не «розкри-
тих» вершин графа, такі шляхи зберіга-
ються в черзі з пріоритетом, де пріоритет
визначається за значенням )(nf . Алго-
ритм продовжує свою роботу до тих пір,
доки не досягне цільової вершини і не ви-
значить шлях до неї з найменшим значен-
Математичне моделювання об’єктів та процесів
122
ням )(nf . Недоліком алгоритму А* є те,
що евристичні оцінки вартості шляхів за-
дані остаточно і не можуть бути змінені в
процесі роботи алгоритму (без його пере-
запуску), що не дозволяє коректно плану-
вати шляхи в середовищі, яке динамічно
змінюється.
Алгоритм D* за назвою походить
від терміну «динамічний А*», оскільки цей
алгоритм подібний алгоритму А* за виня-
тком того, що ваги ребер можуть змінюва-
тись в процесі виконання алгоритму. На
відміну від алгоритму А*, в алгоритмі D*
пошук шляхів виконується від цільової ве-
ршини. При цьому на зваженому графі шу-
кається шлях мінімальної вартості. Якщо в
процесі руху агента по такому шляху ви-
являються перешкоди, то алгоритм змінює
ваги відповідних ребер і динамічно пере-
визначає оптимальний шлях, враховуючи
нову інформацію. Процес повторюється до
тих пір, доки агент не досягне цільової ве-
ршини, або з’ясує, що це неможливо.
4. Постановка задач досліджень
На даному етапі досліджень ми роз-
глядаємо проблему SMAP (див. вступ) для
випадку одного агента. При цьому ми за-
уважуємо, що технічні аспекти вирішення
цієї проблеми виходять за рамки даних до-
сліджень, тобто вважаємо, що вирішення
задач точної локалізації, одометрії, усу-
нення похибок при визначенні кутів пово-
ротів та відстаней до об’єктів оточуючого
середовища, стосуються якості функціону-
вання GPS-обладнання, одометрів і сенсо-
рів та вирішуються на рівні апаратного за-
безпечення досліджуваних процесів. На-
шими задачами є теоретичні аспекти вирі-
шення проблеми SMAP, які на даному ета-
пі досліджень полягають у розробці мето-
дів і моделей коректного вирішення задач
одночасної побудови мапи невідомого ото-
чуючого середовища та планування шляху
в ньому для випадку одного агента, на як-
ість дій якого не впливають вищезгадані
похибки вимірювання, тобто який в кож-
ний момент часу точно знає своє місцезна-
ходження та спроможний використовувати
власні алгоритми для коректного розпізна-
вання невідомого оточуючого середовища
та навігації у ньому.
Для постановки задач досліджень
будемо виходити з наступних припущень:
● оточуючим середовищем для
агента є будівлі ортогональної конфігура-
ції в 2D проекції з довільною кількістю
стін та отворів;
● оточуюче середовище і агент
знаходяться в єдиній Декартовій системі
координат.
Будемо вважати, що завжди існує
мапа M оточуючого середовища як фізи-
чного об’єкта, яка невідома агенту і яку він
має розпізнати, на основі чого побудувати
власну мапу цього середовища. Мапа M
описує множину довільних фрагментів
стін, які фактично існують у межах ото-
чуючого середовища. Підкреслимо, що за-
вдання мапи як множини фрагментів стін
не є випадковим, – таким чином ми нама-
гаємось формалізувати процес сприйняття
досліджуваного оточуючого середовища
людиною: внаслідок властивостей зору,
людина не може, наприклад, одномомент-
но сприйняти всю стіну цілком, а сприй-
має її як послідовність фрагментів. Вихо-
дячи з цього,
},,,{ 21 nwwwM ,
де Mwyxyxidw i
iiii
ii ,),(),,(, 2211 , iid
– унікальний ідентифікатор iw .
Задача r розпізнавання невідомого
оточуючого середовища та навігації у
ньому може бути описана як
aaa
r
GTMM ,, ,
де aM – мапа оточуючого середовища,
побудована агентом a в результаті розпі-
знавання цього середовища та навігації у
ньому; aT – траєкторія руху агента a ,
сформована ним у процесі вирішення за-
дач розпізнавання оточуючого середовища
та навігації у ньому; aG – граф простору
пошуку шляхів, сформований агентом a у
процесі розпізнавання оточуючого середо-
вища та навігації у ньому.
Мапа
},,,{ 21 ma wrwrwrM ,
Математичне моделювання об’єктів та процесів
123
де ),(),,(, 2211
jjjj
jj yxyxidrwr , jwr
aM , jidr – унікальний ідентифікатор
jwr . Мапа aM включає множину розпі-
знаних стін jwr , кінці ),(),,( 2211
jjjj
yxyx
яких, на відміну від фрагментів стін, що
належать мапі M , обов’язково утворюють
деякі кути приміщення, що розпізнається.
Будемо умовно розрізняти внутрішні та
зовнішні кути приміщення (див. рис. 3).
Внутрішні кути відповідають так званим
«глухим» кутам у приміщенні, головною
ознакою яких є те, що вони унеможлив-
люють подальший рух агента в їх напрям-
ку. На відміну від цих кутів, головна озна-
ка зовнішніх кутів – те, що кожний з них є
кутом деякого отвору, через який агент
може перейти в інше приміщення або в
іншу частину даного приміщення; вияв-
лення таких кутів важливо для вирішення
задач планування агентом своїх подаль-
ших шляхів (формування графа aG ).
На рис. 3 показано приклад вияв-
лення внутрішніх та зовнішніх кутів у до-
вільному приміщенні, та умовно показано
отвори (A – B, C – D, E – F, G – H), що від-
повідають виявленим зовнішнім кутам
(або їх парним точкам).
Для розпізнавання оточуючого се-
редовища та побудови мапи aM агент у
кожний момент часу свого руху направляє
промені в оточуюче середовище (вважати-
мемо, що таким чином ми моделюємо
«технічний зір» агента, що на практиці
реалізується за допомогою відповідних
сенсорів), причому крок цих променів має
динамічно змінюватись у процесі розпі-
знавання. Дійсно, якщо крок променів
прийняти постійним, то можуть виникати
ситуації «загублення» інформації.
На рис. 4, а показано випадок, коли
агент розташований у різних точках А та В
отримує на вхід («бачить») різну інформа-
цію про оточуюче середовище, що відпо-
відає ситуації, коли крок променя постій-
ний, в результаті чого агент у позиції В не
«бачить» отвору. На рис. 4, б показано ви-
падок динамічної зміни кроку променя, в
результаті чого незалежно від місця роз-
ташування агент отримує на вхід однакову
інформацію про оточуюче середовище.
Таким чином ми намагаємось врахувати
властивості зору людини, пов’язані з ако-
модацією очей при розгляді об’єктів на рі-
зних відстанях (при цьому відбувається
зміна фокусної відстані ока).
Неформально процес розпізнавання
оточуючого середовища та побудови мапи
агентом полягає у тому, що на кожному
кроці свого руху у вільному просторі ото-
чуючого середовища агент з певним змін-
ним кроком направляє промені відносно
себе та визначає відстані до найближчих
об’єктів (перешкод) оточуючого середо-
вища, що належать мапі M , та координати
точок перетинів променя та перешкоди.
Рис. 3. Приклади кутів у довільному приміщенні
Математичне моделювання об’єктів та процесів
124
AB
B A
а б
Рис. 4. Приклади різних розташувань агента та напрямів променів
Внаслідок того, що промені направляють-
ся послідовно, агент узагальнює коорди-
нати перетинів, отримані від попередніх
променів та поточного променя, та фор-
мує відповідні елементи оточуючого се-
редовища як компоненти мапи aM . В
процесі формування мапи агент аналізує
сформовані компоненти на можливість
утворення ними отворів. Якщо отвір ви-
явлено, агент додає до графа aG новий
фрагмент шляху у складі двох його поча-
ткових елементів.
Очевидно, що запропоноване по-
дання мапи можна розглядати як комбіна-
цію геометричного подання та подання, за-
снованого на орієнтирах (див. п. 2 статті).
Траєкторія aT руху агента містить
множину послідовних за часом позицій
агента, сформованих ним у процесі руху в
середовищі:
},,,{ 21 sa posposposT ,
де ttttt vyxpos ,),,( , at Tpos . Тут
),( tt yx – координати розташування агента
а в момент часу t ; t – кут напряму руху
агента а в момент часу t ; tv – швидкість
руху агента а в момент часу t . Зазначимо,
що оскільки як оточуюче середовище роз-
глядаються довільні будівлі ортогональ-
ної конфігурації, то для моделювання на-
пряму руху (кута t ) агента будемо розг-
лядати тільки 4 варіанти: «праворуч» (кут
руху 0º), «уверх» (кут руху 90º), «ліворуч»
(кут руху 180º), «униз» (кут руху 270º).
Для вирішення проблеми локалізації бу-
демо виходити з вимог, що відповідають
локальній локалізації (див. п. 2 статті),
тобто агент на початку свого руху (в мо-
мент часу 0t ) «знає» своє місцезнахо-
дження (координати ),(
00 tt yx ), а в пода-
льшому визначає його алгоритмічно. Бу-
демо вважати, що швидкість tv руху аген-
та а може бути змінною (у тому числі й
нульовою), оскільки в загальному випадку
він може, наприклад, зупинятися при зу-
стрічі з іншим динамічним об’єктом.
Граф aG простору пошуку шляхів
може бути описаний як кінцева множина
упорядкованих фрагментів шляхів, сфор-
мованих агентом у процесі розпізнавання
невідомого оточуючого середовища та на-
вігації у ньому:
},,,{ 21 qa PathPathPathG ,
де ak GPath – упорядкована послідов-
ність координат позицій агента, займаних
ним у процесі розпізнавання окремої час-
тини невідомого оточуючого середовища.
Кожний ak GPath виступає як ребро
графа aG ; максимально можлива кіль-
кість ребер q у такому графі дорівнює
12 Z , де Z – загальна кількість отворів,
що належать до оточуючого середовища,
яке розпізнається. Зазначимо, що процес
формування графа простору пошуку шля-
хів доцільно виконувати, враховуючи ви-
користовуваний принцип, за яким на та-
кому графі буде виконуватись пошук.
В нашому випадку як метод пошу-
ку на графі обрано пошук у глибину,
оскільки, як показано в п. 3.2, він має пе-
реваги з точки зору використовуваної
Математичне моделювання об’єктів та процесів
125
пам’яті, необхідної для обробки графа.
Нагадаємо, що такий граф має будуватися
та оброблятися за принципом LIFO.
Для ілюстрації процесу формуван-
ня графа aG розглянемо приклад на
рис. 5. На рисунку «хрестики» позна-
чають позиції, відвідані агентом, «круж-
ки» – позиції, заплановані агентом для
відвідання в процесі подальшого обходу
графа.
Припустимо, що агент розпізнав
Отвір 1 та рухається під кутом 90º в Дека-
ртовій системі координат і в процесі по-
дальшого розпізнавання середовища фор-
мує траєкторію руху, послідовно займаю-
чи координати позицій
),(,),,(),,( 12111 byxyxyx та формуючи при
цьому фрагмент шляху 1_1Path , який
включається до складу графа aG . В мо-
мент часу, коли агент досяг координати
),( 1 byx , він розпізнає Отвір 2, і за прин-
ципом LIFO додає до графа aG фрагмент
нового шляху 2Path у складі координат
його майбутніх запланованих позицій
)},(),,{( 12 bb yxyx , тобто на цей момент
часу граф простору пошуку шляхів прий-
ме вигляд },{ 1_12 PathPathGa . Про-
довжуючи подальший рух, агент формує
шлях )},(,),,{( 112_1 bc yxyxPath , який
включається до складу графу aG за прин-
ципом LIFO, в деякий момент часу дося-
гаючи координати ),( 1 cyx та розпізнаючи
Отвір 3, у результаті чого додає до графа
aG фрагмент нового шляху 3Path у складі
координат його майбутніх запланованих
позицій )},(),,{( 13 cc yxyx . При цьому пос-
лідовність шляхів, що формують граф aG ,
прийме наступний вигляд:
},,,{ 1_122_13 PathPathPathPathGa .
Подальший рух агента призведе до посту-
пового додавання відповідних координат
до складу шляхів, а шляхів – до складу
графа aG , і в позиції агента ),( 1 gyx оста-
точний склад графа aG , сформований за
Рис. 5. Приклад формування графу пошуку шляхів
Математичне моделювання об’єктів та процесів
126
результатами планування шляхів у дослі-
джуваному приміщенні, прийме наступний
вигляд:
,,,,,{ 3_144_155_1 PathPathPathPathPathGa
},,, 1_122_13 PathPathPathPath .
Виходячи з даного прикладу, легко помі-
тити, що побудована послідовність фраг-
ментів шляхів відповідає графу простору
пошуку шляхів, в якому кожне ребро від-
повідає окремому фрагменту шляху, а вну-
трішні вершини – загальним елементам
цих шляхів. Також легко помітити, що по-
дальший пошук на сформованому графі
може бути виконаний за допомогою мето-
ду пошуку в глибину.
Таким чином, виходячи з вищеви-
кладеного, можна сформулювати наступ-
ний перелік методів, які необхідно розро-
бити на даному етапі досліджень:
- метод визначення агентом відс-
тані до найближчого від нього об’єкта та
координат перетину з цим об’єктом про-
меня, направленого від агента;
- метод динамічної зміни агентом
кроку променя, який ним направляється в
оточуюче середовище;
- методи розпізнавання агентом
кутів приміщень в оточуючому середови-
щі;
- методи узагальнення агентом
кутів приміщень з виявленням отворів у
оточуючому середовищі;
- методи узагальнення агентом
інформації про оточуюче середовище з по-
будовою мапи цього середовища;
- методи формування агентом
траєкторії руху, що ґрунтуються на враху-
ванні ним узагальненої інформації про
оточуюче середовище;
- методи планування агентом
шляхів пошуку, що ґрунтуються на враху-
ванні ним узагальненої інформації про
оточуюче середовище.
Висновки
У статті виконано аналітичний
огляд проблеми розпізнавання невідомого
оточуючого середовища, навігації та пла-
нування шляхів агентом у ньому та ви-
значено місце наших досліджень в рамках
вирішення цієї проблеми. Обґрунтовано,
що обраний нами напрям досліджень на-
лежить до проблеми одночасної побудови
мапи та планування шляхів (simultaneous
mapping and planning (SMAP)). Виходячи
із структури досліджуваної проблеми, ро-
зглянуто сутність проблеми локалізації та
визначено підхід до вирішення цієї про-
блеми в рамках виконуваних досліджень.
Виконано огляд відомих підходів до по-
будови та подання мапи оточуючого се-
редовища та розглянуто основні сучасні
підходи до формування шляхів пошуку на
мапі й основні методи планування шляхів.
На основі цих оглядів запропоновано но-
ву постановку задач досліджень, в якій
для подання мапи використовується під-
хід, який може розглядатися як комбіна-
ція геометричного подання та подання,
заснованого на орієнтирах, а для подання
простору пошуку використовується гра-
фове подання, що за правилами побудови
відрізняється від інших відомих підходів з
формування графа пошуку. Як випливає з
запропонованої постановки задачі, вона
належить до проблематики SMAP, оскіль-
ки виходячи з неї агент одночасно здійс-
нює побудову мапи оточуючого середо-
вища та планування шляхів.
Література
1. Stachniss C. Robotic Mapping and Explora-
tion. Springer. 2009. 196 p.
2. Makarenko A.A., Williams S.B., Bourgault
F., Durrant-Whyte H.F. An Experiment in In-
tegrated Exploration. Proceedings of the 2002
IEEE/RSJ International Conference on Intel-
ligent Robots and Systems. EPFL. Switzer-
land, 2002. P. 534–539.
3. Durrant-Whyte H., Bailey T. Simultaneous
Localization and Mapping: Part I. IEEE Ro-
botics & Automation Magazine. 2006.
Vol. 13, Iss. 2. P. 99–108.
4. Bailey T., Durrant-Whyte H. Simultaneous
Localization and Mapping: Part II. IEEE Ro-
botics & Automation Magazine. 2006.
Vol. 13. Iss. 3. P. 108–117.
5. Thrun S., Burgard W., Fox D. Probabilistic
Математичне моделювання об’єктів та процесів
127
Robotics. MIT Press. 2006. 647 p.
6. Siegwart R., Nourbakhsh I.R., Scaramuzza D.
Introduction to Autonomous Mobile Robots.
MIT Press. 2011. 453 p.
7. Wallgrün J.O. Hierarchical Voronoi Graphs:
Spatial Representation and Reasoning for
Mobile Robots. Springer, 2010. 218 p.
8. Latombe J.C. Robot motion planning. Spring-
er Science + Business Media, LLC. 1991.
651 p.
9. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн
К. Алгоритмы: построение и анализ. М.:
Вильямс, 2013. 1329 с.
10. LaValle S.M. Planning Algorithms. Cam-
bridge University Press. 2006. 826 p.
References
1. Stachniss C. Robotic Mapping and Explora-
tion. Springer. 2009. 196 p.
2. An Experiment in Integrated Exploration /
Makarenko A.A., Williams S.B., Bourgault
F., Durrant-Whyte H.F. // Proceedings of the
2002 IEEE/RSJ International Conference on
Intelligent Robots and Systems. EPFL. Swit-
zerland, 2002. P. 534–539.
3. Durrant-Whyte H., Bailey T. Simultaneous
Localization and Mapping: Part I // IEEE Ro-
botics & Automation Magazine. Vol.13.
Iss. 2. 2006. P. 99–108.
4. Bailey T., Durrant-Whyte H. Simultaneous
Localization and Mapping: Part II // IEEE
Robotics & Automation Magazine. Vol. 13.
Iss. 3. 2006. P. 108–117.
5. Thrun S., Burgard W., Fox D. Probabilistic
Robotics. MIT Press. 2006. 647 p.
6. Siegwart R., Nourbakhsh I.R., Scaramuzza D.
Introduction to Autonomous Mobile Robots.
MIT Press. 2011. 453 p.
7. Wallgrün J.O. Hierarchical Voronoi Graphs:
Spatial Representation and Reasoning for
Mobile Robots. Springer, 2010. 218 p.
8. Latombe J.C. Robot motion planning.
Springer Science + Business Media, LLC.
1991. 651 p.
9. Cormen T., Leiserson Ch., Rivest R.,
Stein C. Introduction to Algorithms. M.
Williams. 2013. 1329 p. (in Russian)
10. LaValle S.M. Planning Algorithms. Cam-
bridge University Press. 2006. 826 p.
Одержано 10.01.2018
Про автора:
Яловець Андрій Леонідович,
доктор технічних наук,
заступник директора інституту.
Кількість наукових публікацій в
українських виданнях – понад 100.
Кількість наукових публікацій в
зарубіжних виданнях – 10.
http://orcid.org/0000-0001-6542-3483.
Місце роботи автора:
Інститут програмних систем
НАН України.
03187, Київ-187,
проспект Академіка Глушкова, 40.
Тел.: (044) 526 15 38.
E-mail: yal@isofts.kiev.ua
http://orcid.org/0000-0001-6542-3483
mailto:yal@isofts.kiev.ua
|