Methods of recognition by the agent of the unknown environment

The methods used by the agent to recognize an unknown environment are outlined. They include: a method for determining the distance to the nearest visible object and the coordinates of the intersection with this object of the beam (as a simulated direction of the agent's view) directed from the...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2019
Автор:	Yalovets, A.L.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2019
Теми:	agent unknown environment semantic map UDC 004.94+004.896
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/350
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-350
record_format	ojs
resource_txt_mv	ppisoftskievua/8c/949b86cb93f3ede9af259d05bc9d358c.pdf
spelling	pp_isofts_kiev_ua-article-3502024-04-28T11:00:18Z Methods of recognition by the agent of the unknown environment Методы распознавания агентом неизвестной окружающей среды Методи розпізнавання агентом невідомого середовища Yalovets, A.L. agent; unknown environment; semantic map UDC 004.94+004.896 агент; неизвестная окружающая среда; семантическая карта УДК 004.94+004.896 агент; невідоме навколишнє середовище; семантична мапа УДК 004.94+004.896 The methods used by the agent to recognize an unknown environment are outlined. They include: a method for determining the distance to the nearest visible object and the coordinates of the intersection with this object of the beam (as a simulated direction of the agent's view) directed from the agent; the method of dynamically changing the gradation of the beam angle directed by the agent into the environment; a method for constructing a set of points belonging to objects of the environment visible from the point of the current location of the agent; the method of agent's summarizing a set of points with the construction of semantic map fragments of unknown environment; methods of recognition of the corners of rooms in the environment.Problems in programming 2019; 1: 78-89 Изложены методы, используемые агентом для распознавания неизвестной окружающей среды, в том числе: метод определения расстояния до ближайшего видимого объекта и координат пересечения с этим объектом луча (как моделируемого направления зрения агента), направленного от агента; метод динамического изменения градации угла луча, направляемого агентом в окружающую среду; метод построения множества точек, принадлежащим видимым с точки текущего расположения агента объектам окружающей среды; метод обобщения агентом множества точек с построением фрагментов семантической карты неизвестной окружающей среды; методы распознавания углов помещений в окружающей среде.Problems in programming 2019; 1: 78-89 Викладено методи, що використовуються агентом для розпізнавання невідомого навколишнього середовища, в тому числі: метод визначення відстані до найближчого видимого об’єкта та координат перетину з цим об’єктом променя (як модельованого напряму зору агента), направленого від агента; метод динамічної зміни градації кута променя, який направляється агентом у навколишнє середовище; метод побудови множини точок, що належать видимим з точки поточного розташування агента оточуючим об’єктам навколишнього середовища; метод узагальнення агентом множини точок з побудовою фрагментів семантичної мапи невідомого навколишнього середовища; методи розпізнавання кутів приміщень у навколишньому середовищі.Problems in programming 2019; 1: 78-89 Інститут програмних систем НАН України 2019-03-26 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/350 10.15407/pp2019.01.078 PROBLEMS IN PROGRAMMING; No 1 (2019); 78-89 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2019); 78-89 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2019); 78-89 1727-4907 10.15407/pp2019.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/350/355 Copyright (c) 2019 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2024-04-28T11:00:18Z
collection	OJS
language	Ukrainian
topic	agent unknown environment semantic map UDC 004.94+004.896
spellingShingle	agent unknown environment semantic map UDC 004.94+004.896 Yalovets, A.L. Methods of recognition by the agent of the unknown environment
topic_facet	agent unknown environment semantic map 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	Methods of recognition by the agent of the unknown environment
title_short	Methods of recognition by the agent of the unknown environment
title_full	Methods of recognition by the agent of the unknown environment
title_fullStr	Methods of recognition by the agent of the unknown environment
title_full_unstemmed	Methods of recognition by the agent of the unknown environment
title_sort	methods of recognition by the agent of the unknown environment
title_alt	Методы распознавания агентом неизвестной окружающей среды Методи розпізнавання агентом невідомого середовища
description	The methods used by the agent to recognize an unknown environment are outlined. They include: a method for determining the distance to the nearest visible object and the coordinates of the intersection with this object of the beam (as a simulated direction of the agent's view) directed from the agent; the method of dynamically changing the gradation of the beam angle directed by the agent into the environment; a method for constructing a set of points belonging to objects of the environment visible from the point of the current location of the agent; the method of agent's summarizing a set of points with the construction of semantic map fragments of unknown environment; methods of recognition of the corners of rooms in the environment.Problems in programming 2019; 1: 78-89
publisher	Інститут програмних систем НАН України
publishDate	2019
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/350
work_keys_str_mv	AT yalovetsal methodsofrecognitionbytheagentoftheunknownenvironment AT yalovetsal metodyraspoznavaniâagentomneizvestnojokružaûŝejsredy AT yalovetsal metodirozpíznavannâagentomnevídomogoseredoviŝa
first_indexed	2024-09-16T04:08:35Z
last_indexed	2024-09-16T04:08:35Z
_version_	1818568456464760832
fulltext	Математичне моделювання об’єктів та процесів © А.Л. Яловець, 2019 78 ISSN 1727-4907. Проблеми програмування. 2019. № 1 УДК 004.94+004.896 https://doi.org/10.15407/pp2019.01.078 А.Л. Яловець МЕТОДИ РОЗПІЗНАВАННЯ АГЕНТОМ НЕВІДОМОГО НАВКОЛИШНЬОГО СЕРЕДОВИЩА Викладено методи, що використовуються агентом для розпізнавання невідомого навколишнього сере- довища, в тому числі: метод визначення відстані до найближчого видимого об’єкта та координат пере- тину з цим об’єктом променя (як модельованого напряму зору агента), направленого від агента; метод динамічної зміни градації кута променя, який направляється агентом у навколишнє середовище; метод побудови множини точок, що належать видимим з точки поточного розташування агента оточуючим об’єктам навколишнього середовища; метод узагальнення агентом множини точок з побудовою фраг- ментів семантичної мапи невідомого навколишнього середовища; методи розпізнавання кутів примі- щень у навколишньому середовищі. Ключові слова: агент, невідоме навколишнє середовище, семантична мапа. Вступ В роботі [1] виконано постановку задачі розпізнавання невідомого навколи- шнього середовища, яка, зокрема, включає до свого складу задачу побудови агентом мапи цього середовища. Слід зауважити, що виконана постановка задачі за своїм змістом передбачала побудову «семантич- ної мапи» навколишнього середовища, під якою розуміється [2] мапа, яка додатково до просторової інформації про навколишнє середовище також містить семантичні вла- стивості, зіставлені сутностям відомих класів, розташованим на мапі. Такі семан- тичні властивості дозволяють розрізнити, зокрема, як типи приміщень (наприклад, кімнату від коридору), так і об’єкти, що розташовані у приміщеннях (наприклад, столи від стільців). Виходячи з цього, від- повідно до переліку задач досліджень, сформульованих в [1], в даній статті ви- кладено методи розпізнавання агентом не- відомого навколишнього середовища, на основі яких агент будує семантичну мапу цього середовища. До таких методів, зок- рема, належать: метод визначення агентом відстані до найближчого до нього видимо- го об’єкта та координат перетину з цим об’єктом променя (як модельованого на- пряму зору агента), направленого від аген- та; метод динамічної зміни агентом града- ції кута променя, який ним направляється в навколишнє середовище; метод побудо- ви агентом множини точок, що належать видимим з точки поточного розташування агента оточуючим об’єктам навколишньо- го середовища, отриманих в результаті направлення ним в навколишнє середови- ще променів з визначеним змінним кутом; метод узагальнення агентом множини то- чок з побудовою фрагментів семантичної мапи невідомого навколишнього середо- вища; методи розпізнавання кутів примі- щень у навколишньому середовищі. 1. Метод визначення відстані до найближчого видимого об’єкта Припустимо, що рухомому агенту необхідно розпізнати видимі об’єкти, що його оточують. Для цього він у кожний момент часу свого руху сканує оточуюче його середовище, послідовно направляючи відносно себе промені з певним кроком кутів. Розглянемо довільну ситуацію, коли агент у деякий момент часу розташований у точці A і з метою розпізнавання оточу- ючих його об’єктів сформував промінь AB для визначення відстані (довжини прямої AE ) до найближчого об’єкта та координат хЕ, уЕ точки перетину променя з цим об’єктом точки E (рис. 1). Також припустимо, що на даному рисунку нам відомі тільки координати трьох точок ( A , С, D) та кут αAB напряму променя щодо поточного розташування агента (точки A ) в Декартовій системі ко- ординат та координата хB «глибини» скану- вання навколишнього середовища («гли- бина» сканування визначається на почат- ковому етапі розпізнавання), де C, D – http://dx.doi.org/10.7124/bc.000027 Математичне моделювання об’єктів та процесів 79 C αAD YA YD XD XA A D B E E1 B1 αAB β1 αDB αDA β2 αDC β3 yE xE xB Рис. 1. Схема розташування агента щодо об’єкта, що потребує розпізнавання координати меж деякого лінійного об’єкта, що потребує розпізнавання (які зберіга- ються у БД опису навколишнього середо- вища). Кінцева мета процесу розпізнавання навколишнього середовища агентом поля- гає у формуванні ним власної БД опису навколишнього середовища. Виконаємо необхідні добудови. Прокладемо осі координат щодо точок A і D (вважаємо, що агент функціонує в декартовій системі координат). З’єднаємо точки A , D та B , D прямими, а з точок Е і B проведемо пер- пендикуляри на пряму AD . Очевидно, що утворені при цьому трикутники 1AEE та 1ABB є подібними і для них справедливе співвідношення: 1 1 EE BB AE AB  , (так як AE EE1 1sin  та AB BB1 1sin  ). Звідси маємо шукану довжину AE : 1 1 BB EEAB AE   . (1) Знаючи AE , легко визначити шукані ко- ординати хЕ та уЕ ( ABE AEx cos ; ABE AEy sin ). У виразі (1) нам невідомі 1EE та 1BB . Для визначення 1BB розглянемо прямокутний трикутник 1DBB , в якому нам відомі гіпотенуза ВD та кут 2 (де DBDA  2 ). Звідси 21 sin  BDBB . Для визначення 1EE розглянемо два прямокутних трикутника 1AEE та 1DEE , у яких є загальний катет 1EE . Кути 1 ( ADAB  1 ) та 3 ( 3 DCDA   ) відомі. Враховуючи, що ADDEAE  11 , та приймаючи xAE 1 , маємо:  1tgx 3)( tgxAD  . Звідси 31 3   tgtg tg ADx   . Враховуючи, що 111 tgAEEE  , маємо: 31 31 1   tgtg tgtg ADEE    , Математичне моделювання об’єктів та процесів 80 або, після перетворень: )sin( sinsin 31 31 1      ADEE . Перетворюючи вираз (1), остаточно маємо: )sin(sin sinsin 312 31      BD AD ABAE . (2) Тоді )sin(sin sinsincos 312 31      AB E BD AD ABx , )sin(sin sinsinsin 312 31      AB E BD AD ABy . (3) Оскільки агент може рухатись у рі- зних напрямах і об’єкти, що потребують розпізнавання, можуть розташовуватись з різних сторін від нього, то формули визна- чення кутів 321 ,,  будуть різними у ко- жному окремому випадку (таблиця). Таблиця. Класифікація ситуацій розпізнавання агентом оточуючих об’єктів № сит. Напрям променя / розташування стіни Примітки 1 2 3 4 1 Промінь у IV октанті; стіна горизонтальна β1 = αAD – αAB β2 = αDB – αDA β3 = 180º – αDA 2 Промінь у IV октанті; стіна вертикальна β1 = αAB – αAD β2 = αDA – αDB β3 = αDA – αDC 3 Промінь на стику I і IV октантів; стіна верти- кальна β1 = 360º – αAD β2 = αDA – αDB β3 = αDA – 90º 4 Промінь у I октанті; стіна вертикальна β1 = (360º – αAD) + αAB β2 = αDA – αDB β3 = αDA – 90º 5 Промінь у I октанті; стіна горизонтальна β1 = αAB – αAD β2 = αDA – αDB β3 = αDA – 180º D C B A B A C D B A C D B A C D D C B A Математичне моделювання об’єктів та процесів 81 Закінчення таблиці 1 2 3 4 6 Промінь на стику I і II октантів; стіна горизо- нтальна β1 = 90º – αAD β2 = αDA – αDB β3 = αDA – 180º 7 Промінь у II октанті; стіна горизонтальна β1 = αAB – αAD β2 = αDA – αDB β3 = αDA – 180º 8 Промінь у II октанті; стіна вертикальна β1 = αAD – αAB β2 = αDB – αDA β3 = 90º – αDA 9 Промінь на стику II і III октантів; стіна верти- кальна β1 = αAD – 180º β2 = αDB – αDA β3 = 90º – αDA 10 Промінь у III октанті; стіна вертикальна β1 = αAD – αAB β2 = αDB – αDA β3 = 90º – αDA 11 Промінь у III октанті; стіна горизонтальна β1 = αAD – αAB β2 = αDB – αDA β3 = 180º – αDA 12 Промінь на стику III і IV октантів; стіна гори- зонтальна β1 = αAD – 270º β2 = αDB – αDA β3 = 180º – αDA D C B A D C B A B A C D B A C D B A C D D C B A D C B A Математичне моделювання об’єктів та процесів 82 Отже, в результаті виконання кла- сифікації виявлено дванадцять унікальних ситуацій розпізнавання агентом об’єктів спостережуваного навколишнього середо- вища. 2. Метод динамічної зміни агентом градації кута променя, який ним направляється в навколишнє середовище Метод ґрунтується на поєднанні ідей, що лежать в основі кліткової деком- позиції та обробки графу огляду [1]. У випадку, коли градація кута променя є по- стійною, агент може втрачати інформацію [1]. Як наслідок, для забезпечення потріб- ної якості формування інформації агентом про навколишнє середовище необхідно, щоб ця градація динамічно змінювалась у залежності від відстані до об’єкта, що спостерігається агентом. При цьому, як зауважено в [1], за постановкою задач до- сліджень навколишнім середовищем для агента є будівлі ортогональної конфігура- ції в 2D проекції з довільною кількістю стін та отворів. Відомо, що для таких бу- дівель властива певна модульність геоме- тричних розмірів їх складових (як стін, так і отворів). Для вирішення задачі ди- намічної зміни агентом градації кута про- меня доцільно ввести поняття модуля (де розміри стін та отворів будуть кратними його значенню), який буде використову- ватись для розбиття простору, що відпо- відає навколишньому середовищу агента, на клітинки, де розмір кожної її сторони буде відповідати значенню модуля (оче- видно, що цей підхід подібний за своєю ідеєю сутності підходу кліткової деком- позиції). Отже, на рис. 2 показано, що агенту необхідно визначити градацію кута  як       X H arctan , де Н – розмір сторони клітинки (значення модуля), X – макси- мальне значення по осі Х відстані до най- ближчого об’єкта, видимого з точки пото- чного розташування агента (в загальному випадку – це максимальне значення різ- ниці між координатами X (або Y) точки перетину променя з таким об’єктом та ко- ординатами розташування агента). Δα H X Рис. 2. Приклад визначення значення гра- дації кута огляду агента 3. Метод побудови агентом множини точок, що належать видимим агенту оточуючим об’єктам навколишнього середовища Метод ґрунтується на тому, що агент послідовно направляє промені проти часової стрілки, кожного разу змінюючи кут на обчислюване значення  , та ви- значаючи (за допомогою виразів (3)) коор- динати точок перетину променів з най- ближчими видимими об’єктами. Як наслі- док, у агента формується множина коор- динат таких точок, що є упорядкованою (як і у випадку обробки графу огляду), і тому дозволяє стверджувати, що подаль- ший послідовний аналіз таких точок до- зволить згенерувати семантичну мапу на- вколишнього середовища. На рис. 3 по- казано процес формування агентом мно- жини точок, що належать видимим агенту об’єктам навколишнього середовища, ви- конуваний засобами мультиагентної сис- теми (МАС) САГА, призначеної для моде- лювання поведінки агентів (у тому числі побудови семантичної мапи) у невідомому навколишньому середовищі. Як видно з цього рисунку, градація кута огляду агента є змінною. 4. Метод узагальнення агентом множини точок з побудовою фрагментів семантичної мапи невідомого навколишнього середовища Як зазначено у вступі, під «семан- тичною мапою» навколишнього середо- вища розуміється [2] мапа, яка додатково до просторової інформації про навколи- шнє середовище також містить семанти- чні властивості, зіставлені сутностям ві- домих класів, розташованим на мапі. Бу- демо вважати базовими сутностями, що Математичне моделювання об’єктів та процесів 83 Рис. 3. Процес формування агентом множини точок розташовані на мапі та необхідні для розпізнавання більш складних сутностей, стіни та отвори, які належать приміщен- ням, що розпізнаються. Тобто на почат- ковому етапі процесу побудови семанти- чної мапи агенту необхідно сформувати фрагменти цієї мапи у вигляді стін та отворів, а далі, шляхом узагальнення цієї інформації, отримати більш загальну се- мантичну інформацію про навколишнє середовище (типи приміщень тощо). На даному етапі будемо вважати, що процес створення семантичної мапи aSM агентом а може бути поданий у ви- гляді кортежу (4):  RPSMa , . (4) Тут P – множина точок, побудо- вана агентом (див. п. 3 статті); R – правила перетворення агентом множини P у фрагменти семантичної мапи (стіни та отвори). Правила R можуть бути структу- ровані на три групи: правила розпізнаван- ня «горизонтальних» стін (у яких збіга- ється координата Y в декартовій системі координат); правила розпізнавання «вер- тикальних» стін (у яких, відповідно, збі- гається координата Х); правила розпізна- вання та обробки ситуацій зміни типу сті- ни («горизонтальної» або «вертикаль- ної»), що «спостерігається» агентом, або геометрії стіни (ці правила відповідають ситуаціям розпізнавання різного роду ку- тів приміщень). Фрагмент лістингу формалізації правил розпізнавання «горизонтальних» стін за допомогою предикатів мови про- грамування Prolog показано на рис. 4. Математичне моделювання об’єктів та процесів 84 Рис. 4. Фрагмент лістингу з формалізації розпізнавання агентом «горизонтальних» стін f_wall(pnt(X1,Y1),pnt(X2,Y2),S,S1):- % предикат f_wall перевіряє дві послідовні точки pnt (з множини точок) і, якщо координати Y у них збігаються, формує дані щодо % «горизонтальної» стіни; S – стан стіни, що розпізнано останньою; S1 – стан стіни, що розпізнається в даний момент часу Y1 = Y2,!, prov_SG(pnt(X1,Y1),pnt(X2,Y2),S,S1). prov_SG(pnt(X1,Y),pnt(X2,Y),S,S1):- % перший клоз предиката prov_SG аналізує випадок, коли відбувається зміна стану стіни (з невизначеної до горизонтальної) S=" ",!, S1="gor", n_w(N), N1=N+1, % перевизначення номеру стіни, що оброблюється retract(n_w(_),envir_w),!, assert(n_w(N1),envir_w), f_w3(N1,Y,X1,X2). prov_SG(pnt(X1,Y),pnt(X2,Y),S,S1):- % другий клоз предиката prov_SG аналізує випадок, коли стан стіни не змінюється S="gor",!, S1=S, f_w4(Y,X1,X2). prov_SG(PNT1,PNT2,S," "):- % третій клоз предиката prov_SG аналізує випадок, коли відбувається зміна стану стіни (з горизонтальної до невизначеної) f_w5(S,PNT1,PNT2),!. f_w3(N,Y,X1,X2):- X2>X1,!, X11 = X1 - step/2.0, X21 = X2 + step/2.0, % step – значення модулю % збереження предикату БД work_w як робочого стану стіни, що оброблюється assert(work_w(N,"Горизонтальна стіна",pnt(X11,Y),pnt(X21,Y)),envir_w). f_w3(N,Y,X1,X2):- X11 = X1 + step/2.0, X21 = X2 - step/2.0, assert(work_w(N," Горизонтальна стіна ",pnt(X11,Y),pnt(X21,Y)),envir_w). f_w4(Y,X1,X2):- abs(X1-X2) = step,!, % стіна продовжується (без отвору) f_w41(Y,X1,X2). f_w4(Y,X1,X2):- % у межах стіни виявлено отвір X2>X1,!, X11 = X1 + step/2.0, work_w(N,S,pnt(X0,Y),_), % вилучення з БД предикату work_w робочого стану стіни та додавання предикату БД wall_r як опису розпізнаної стіни retract(work_w(_,_,_,_),envir_w),!, assert(wall_r(N,S,pnt(X0,Y),pnt(X11,Y)),envir_r), X21 = X2 - step/2.0, n_p(NP), NP1 = NP +1, retract(n_p(_),envir_w),!, assert(n_p(NP1),envir_w), % додавання предикату БД pr_r як опису розпізнаного отвору assert(pr_r(NP1,pnt(X11,Y),pnt(X21,Y)),envir_r), X22 = X21 + step, N1 = N+1, retract(n_w(_),envir_w),!, assert(n_w(N1),envir_w), assert(work_w(N1,S,pnt(X21,Y),pnt(X22,Y)),envir_w). Математичне моделювання об’єктів та процесів 85 На рис. 5 показано приклад розпі- знавання приміщення агентом з форму- ванням ним фрагментів семантичної мапи (з окремої точки розташування агента). На рис. 6 показано фрагмент БД опису навколишнього середовища, сфор- мованого в середовищі МАС САГА вруч- ну шляхом побудови приміщень з окремих семантично не інтерпретованих ліній (від- повідає рис. 3). На рис. 7 показано БД опи- су цього ж навколишнього середовища як фрагментів семантичної мапи, сформова- ної агентом у середовищі МАС САГА (відповідає стінам чорного кольору на рис. 5). Слід підкреслити, що на відміну від БД стін, яка може створюватись з фрагме- нтів ліній і не відповідати за змістом фак- тичній структурі окремої стіни, БД фраг- менту семантичної мапи, як випливає з рис. 7, містить цілісне подання стін як се- мантично завершене. В процесі руху агент постійно уто- чнює і добудовує семантичну мапу (рис. 8, зліва направо). Рис. 5. Процес побудови фрагментів семантичної мапи wall(1,pnt(8360,5080),pnt(8360,5200)) wall(2,pnt(8360,5200),pnt(8160,5200)) wall(4,pnt(8160,5400),pnt(8160,5520)) wall(5,pnt(8160,5520),pnt(8640,5520)) wall(6,pnt(8640,5520),pnt(8640,5480)) wall(7,pnt(8640,5440),pnt(8640,5280)) wall(8,pnt(8640,5240),pnt(8640,5200)) wall(11,pnt(8640,5200),pnt(8400,5200)) wall(12,pnt(8400,5200),pnt(8400,5080)) wall(13,pnt(8400,5080),pnt(8360,5080)) ………………………………………… wall(27,pnt(8160,5280),pnt(8120,5280)) wall(28,pnt(8120,5280),pnt(8120,5240)) wall(29,pnt(8120,5240),pnt(8160,5240)) wall_r(1,"Горизонтальна стіна",pnt(8160,5520),pnt(8640,5520)) wall_r(2,"Горизонтальна стіна",pnt(8640,5480),pnt(8720,5480)) wall_r(3,"Вертикальна стіна",pnt(8640,5440),pnt(8640,5280)) wall_r(4,"Горизонтальна стіна",pnt(8600,5200),pnt(8400,5200)) wall_r(5,"Горизонтальна стіна",pnt(8360,5200),pnt(8160,5200)) wall_r(6,"Вертикальна стіна",pnt(8160,5280),pnt(8160,5360)) wall_r(7,"Горизонтальна стіна",pnt(8080,5400),pnt(8160,5400)) wall_r(8,"Вертикальна стіна",pnt(8160,5400),pnt(8160,5520)) Рис. 6. Фрагмент БД стін Рис. 7. БД фрагменту семантичної мапи Математичне моделювання об’єктів та процесів 86 Рис. 8. Процес добудови семантичної мапи агентом у процесі його руху Процес створення агентом семанти- чної мапи аналізованого приміщення заве- ршується тоді, коли агент вже не може до- дати нової інформації до мапи. Зауважимо, що промені на рис. 3, 5 та 8 показано умо- вно, лише для ілюстрації особливостей процесу розпізнавання навколишнього се- редовища. 5. Методи розпізнавання кутів приміщень в навколишньому середовищі Як зазначено в [1], кути приміщень можна умовно розподілити на два види: внутрішні (відповідають так званим «глу- хим» кутам у приміщенні, головною озна- кою яких є те, що вони унеможливлюють подальший рух агента в їх напрямку) та зовнішні (головною ознакою яких є те, що кожний з них є кутом деякого отвору, че- рез який агент може перейти в інше при- міщення або в іншу частину даного при- міщення). Відповідно до цього розробле- но методи розпізнавання цих двох видів кутів. Для зручності викладення цих ме- тодів розглянемо приклад приміщення на рис. 9, в якому агент розташований у деякій точці А і «спостерігає» навколишнє середовище, направляючи в нього промені з певним змінним кроком. Методи ґрунтуються на наступних правилах прийняття рішень агентом: 1. Агент розпізнає кут приміщення як внутрішній, якщо виконується наступ- на перевірка (рис. 9): AE > 1AE , AE > > 2AE (ці співвідношення також справедли- ві для всіх інших внутрішніх кутів O, L, H). 2. Агент розпізнає кути приміщен- ня як зовнішні, якщо виконується одна з наступних перевірок (рис. 9): 2.1. За умов повної видимості кута (наприклад, кута В), коли два відрізки при їх зведенні дають загальну координату (наприклад, ВВ1 та В2В дають координату В) та виконується наступна перевірка: AB < AB1, AB < AB2 (ці співвідношення також справедливі для кутів D, F, G, J, M, N, P). 2.2. За умов часткової видимості кута, коли два відрізки при їх зведенні не дають загальної координати, можливі два варіанти: 2.2.1. Коли точки перетинів нале- жать прямим, що перпендикулярні одна одній (наприклад, точки 1C та 2C при ви- значенні отвору С – рис. 9), то виконуєть- ся перевірка: 1ACAС  , 2ACAС  (ці співвідношення також справедливі для ку- та K та кутів S, T на рис. 10). Зауважимо, якщо є тільки дві точки ( С , 1C ) і третій промінь не дав точки перетину, то 2AC приймається як нескінченність, і ця пере- вірка також виконується. Математичне моделювання об’єктів та процесів 87 A D D2 D1 C2 C1 C B B2 B1 E E1 E2F1F F2 XA YA G1 G2 GH1 H2 H J1 J2 J K1 K2 K L1 L2L M1 M2 M N1 N2N O1 O2 O P1 P2 P Рис. 9. Схема розпізнавання кутів приміщення агентом, розташованим у точці А A R R1 R2 S S1 S2 T T1 T2 Рис. 10. Фрагмент схеми розпізнавання кутів агентом, розташованим у точці А 2.2.2. Коли точки перетинів нале- жать прямим, що паралельні одна одній (наприклад, точки R1 та R2 при визначенні отвору R – рис. 10), то виконується переві- рка 1ARAR  , 2ARAR  . Висновки Реалізація та використання запро- понованих методів в МАС САГА показало досить високу їх ефективність для вирі- шення задачі розпізнавання агентом не- відомого навколишнього середовища. Не- зважаючи на це, процедура розпізнавання має певні недоліки, усунення яких потре- бує проведення додаткових досліджень. Зокрема, виходячи з цієї процедури, агент спроможний розпізнати стіну, якщо має можливість проаналізувати хоча б дві послідовно розташовані точки, що їй належать. Водночас в реальних обста- винах у нього такої можливості може не бути. Наприклад, на рис. 11 показано випадки (фрагменти мапи, обведені кола- ми), коли агент, використовуючи запро- поновану процедуру розпізнавання, ніколи не зможе завершити формування Математичне моделювання об’єктів та процесів 88 семантичної мапи такого приміщення, оскільки (де б він не знаходився) в нього завжди буде не вистачати необхідної інфо- рмації для завершення процесу розпізна- вання. Крім того, процес розпізнавання отворів у приміщеннях, що засновується на методах розпізнавання кутів примі- щення, теж може давати похибки. Напри- клад (рис. 12), агент, користуючись пра- вилами прийняття рішень, викладеними в п. 5 статті, не зможе коректно визначити кут Q, оскільки ця ситуація (коли точки перетинів належать прямим, що перпен- дикулярні одна одній) відповідає п. 2.2.1 правил, за яким має бути AQ > AQ1, AQ < < AQ2, водночас як за фактом: AQ < AQ1, AQ < AQ2. Отже, запропоновані методи потре- бують відповідних удосконалень. Рис. 11. Приклади відсутності інформації, необхідної для успішного розпізнавання A Q1 Q Q2 Рис. 12. Фрагмент схеми розпізнавання кута агентом, розташованим у точці А Математичне моделювання об’єктів та процесів 89 Література 1. Яловець А.Л. До постановки задачі розпі- знавання невідомого оточуючого середо- вища, навігації та планування шляхів аген- том в ньому. Проблеми програмування. 2018. № 1. С. 113–127. 2. Nüchter A., Hertzberg J. Towards semantic maps for mobile robots. Robotics and Autonomous Systems. 2008. Vol. 56, N 11. P. 915–926. References 1. Yalovets A.L. Statement of problem of unknown environment recognizing, navigating and path planning by agent. Problems in programming. 2018. N 1. P. 113–127 (in Ukrainian). 2. Nüchter A., Hertzberg J. Towards semantic maps for mobile robots. Robotics and Autonomous Systems. 2008. Vol. 56, N 11. P. 915–926. Одержано 11.02.2019 Про автора: Яловець Андрій Леонідович, доктор технічних наук, заступник директора інституту. Кількість наукових публікацій в українських виданнях – понад 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

Methods of recognition by the agent of the unknown environment

Репозитарії

Схожі ресурси