Application of coevolution strategy to solve the problem of autonomous navigation trough the maze

This study explores the use of coevolutionary methods to address the challenge of navigating through complex mazes using autonomous agents controlled by artificial neural networks (ANNs). It underscores a critical impediment to algorithmic optimization: the close interdependence between the task...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2024
Hauptverfasser:	Omelianenko, Ia.V., Doroshenko, A.Yu., Rodin, Ye.S.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут програмних систем НАН України 2024
Schlagworte:	genetic algorithms neuroevolution of augmenting topologies autonomous maze navigation NEAT coevolution UDC 004.8
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/645
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-645
record_format	ojs
resource_txt_mv	ppisoftskievua/50/6ac5489b352d93cf341cf3287d808e50.pdf
spelling	pp_isofts_kiev_ua-article-6452025-02-15T13:43:04Z Application of coevolution strategy to solve the problem of autonomous navigation trough the maze Застосування стратегії коеволюції для вирішення задачі автономного проходження лабіринту Omelianenko, Ia.V. Doroshenko, A.Yu. Rodin, Ye.S. genetic algorithms; neuroevolution of augmenting topologies; autonomous maze navigation; NEAT; coevolution UDC 004.8 генетичні алгоритми; нейроеволюція наростаючих топологій; автономне проходження лабіринту; NEAT; коеволюція УДК 004.8 This study explores the use of coevolutionary methods to address the challenge of navigating through complex mazes using autonomous agents controlled by artificial neural networks (ANNs). It underscores a critical impediment to algorithmic optimization: the close interdependence between the task's goal and the objective function used for optimal solution discovery. The task's goal is clear—identify the most efficient route through the maze. However, the objective function's formulation is more complex. In complex maze layouts, numerous deceptive areas may appear proximate to the exit but culminate in dead ends. Consequently, an elementary objective function that merely gauges the proximity to the exit can encounter numerous local optima within this deceptive search space, hindering the search for optimal solution. As maze complexity increases, such an objective function inevitably becomes ensnared in a local optimum, rendering the navigation issue unsolvable. To counteract this, the study proposes a coevolution strategy involving a population of decision-making agents and a population of objective function candidates. This approach diverges from prior research by incorporating the NEAT algorithm to steer the coevolution of both populations. Additionally, the Novelty Search (NS) method was suggested to optimize the search within the potential solution space, favoring the most novel solutions. The paper details the mathematical framework for crafting the objective function template, which integrates the novelty value of the discovered solution and its distance from the maze's exit. This framework serves as the foundation for defining the genomes of the organisms — candidates for the objective functions. For comparison with preceding works, an experiment was conducted to evaluate the efficacy of the proposed coevolution method in resolving the problem of navigation within a complex maze environment.Prombles in programming 2024; 2-3: 263-270 У статті розглянуто застосування методу коеволюції для вирішення задачі пошуку виходу зі складного лабіринту автономним агентом, що керується штучною нейронною мережею (ШНМ). Вирішення цієї задачі висвітлює фундаментальну проблему, яка перешкоджає алгоритмічній оптимізації – тісне поєднання цілі завдання із цільовою функцією, що використовується для пошуку оптимального рішення. Для вирішення цієї задачі ціль є очевидною – знаходження оптимального шляху крізь лабіринт. У той же час, з цільовою функцією все дещо складніше. В складних конфігураціях лабіринту зазвичай налічується багато оманливих зон, які наближені до точки виходу з лабіринту, але є глухими кутами, що не мають шляху до виходу. Таким чином, проста цільова функція, заснована тільки на вимірюванні відстані до виходу з лабіринту, має багато локальних оптимумів в оманливому просторі пошуку рішення. З підвищенням складності конфігурації лабіринту, проста цільова функція рано чи пізно застряє у одному з локальних оптимумів, що унеможливлює вирішення задачі навігації. Для вирішення цієї проблеми було запропоновано використання стратегії коеволюції популяції агентів-вирішувачів та популяції кандидатів у цільові функції. На відміну від попередніх робіт у цьому напрямку, було запропоновано використання алгоритму NEAT для керування процесом коеволюції обох популяцій. Водночас для оптимізації пошуку у просторі рішень було запропоновано використання методу Novelty Search (NS), який полягає у наданні переваги найбільш інноваційним рішенням. Було наведено опис математичного апарату для визначення шаблону цільової функції, що включає у себе як значення інноваційності рішення, так і значення відстані до виходу з лабіринту. Цей шаблон був взятий за основу при визначенні генному організмів – кандидатів у цільові функції. Для порівняння з попередніми роботами було проведено експеримент для визначення ефективності запропонованого методу коеволюції у вирішенні задачі навігації у складному лабіринті.Prombles in programming 2024; 2-3: 263-270 Інститут програмних систем НАН України 2024-12-17 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/645 10.15407/pp2024.02-03.263 PROBLEMS IN PROGRAMMING; No 2-3 (2024); 263-270 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2024); 263-270 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2024); 263-270 1727-4907 10.15407/pp2024.02-03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/645/697 Copyright (c) 2024 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-02-15T13:43:04Z
collection	OJS
language	Ukrainian
topic	genetic algorithms neuroevolution of augmenting topologies autonomous maze navigation NEAT coevolution UDC 004.8
spellingShingle	genetic algorithms neuroevolution of augmenting topologies autonomous maze navigation NEAT coevolution UDC 004.8 Omelianenko, Ia.V. Doroshenko, A.Yu. Rodin, Ye.S. Application of coevolution strategy to solve the problem of autonomous navigation trough the maze
topic_facet	genetic algorithms neuroevolution of augmenting topologies autonomous maze navigation NEAT coevolution UDC 004.8 генетичні алгоритми нейроеволюція наростаючих топологій автономне проходження лабіринту NEAT коеволюція УДК 004.8
format	Article
author	Omelianenko, Ia.V. Doroshenko, A.Yu. Rodin, Ye.S.
author_facet	Omelianenko, Ia.V. Doroshenko, A.Yu. Rodin, Ye.S.
author_sort	Omelianenko, Ia.V.
title	Application of coevolution strategy to solve the problem of autonomous navigation trough the maze
title_short	Application of coevolution strategy to solve the problem of autonomous navigation trough the maze
title_full	Application of coevolution strategy to solve the problem of autonomous navigation trough the maze
title_fullStr	Application of coevolution strategy to solve the problem of autonomous navigation trough the maze
title_full_unstemmed	Application of coevolution strategy to solve the problem of autonomous navigation trough the maze
title_sort	application of coevolution strategy to solve the problem of autonomous navigation trough the maze
title_alt	Застосування стратегії коеволюції для вирішення задачі автономного проходження лабіринту
description	This study explores the use of coevolutionary methods to address the challenge of navigating through complex mazes using autonomous agents controlled by artificial neural networks (ANNs). It underscores a critical impediment to algorithmic optimization: the close interdependence between the task's goal and the objective function used for optimal solution discovery. The task's goal is clear—identify the most efficient route through the maze. However, the objective function's formulation is more complex. In complex maze layouts, numerous deceptive areas may appear proximate to the exit but culminate in dead ends. Consequently, an elementary objective function that merely gauges the proximity to the exit can encounter numerous local optima within this deceptive search space, hindering the search for optimal solution. As maze complexity increases, such an objective function inevitably becomes ensnared in a local optimum, rendering the navigation issue unsolvable. To counteract this, the study proposes a coevolution strategy involving a population of decision-making agents and a population of objective function candidates. This approach diverges from prior research by incorporating the NEAT algorithm to steer the coevolution of both populations. Additionally, the Novelty Search (NS) method was suggested to optimize the search within the potential solution space, favoring the most novel solutions. The paper details the mathematical framework for crafting the objective function template, which integrates the novelty value of the discovered solution and its distance from the maze's exit. This framework serves as the foundation for defining the genomes of the organisms — candidates for the objective functions. For comparison with preceding works, an experiment was conducted to evaluate the efficacy of the proposed coevolution method in resolving the problem of navigation within a complex maze environment.Prombles in programming 2024; 2-3: 263-270
publisher	Інститут програмних систем НАН України
publishDate	2024
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/645
work_keys_str_mv	AT omelianenkoiav applicationofcoevolutionstrategytosolvetheproblemofautonomousnavigationtroughthemaze AT doroshenkoayu applicationofcoevolutionstrategytosolvetheproblemofautonomousnavigationtroughthemaze AT rodinyes applicationofcoevolutionstrategytosolvetheproblemofautonomousnavigationtroughthemaze AT omelianenkoiav zastosuvannâstrategííkoevolûcíídlâviríšennâzadačíavtonomnogoprohodžennâlabírintu AT doroshenkoayu zastosuvannâstrategííkoevolûcíídlâviríšennâzadačíavtonomnogoprohodžennâlabírintu AT rodinyes zastosuvannâstrategííkoevolûcíídlâviríšennâzadačíavtonomnogoprohodžennâlabírintu
first_indexed	2025-07-17T10:02:43Z
last_indexed	2025-07-17T10:02:43Z
_version_	1838410386442813440
fulltext	263 Машинне навчання та нейронні мережі УДК 004.8 http://doi.org/10.15407/pp2024.02-03.263 Я.В. Омельяненко, А.Ю. Дорошенко, Є.С. Родін ЗАСТОСУВАННЯ СТРАТЕГІЇ КОЕВОЛЮЦІЇ ДЛЯ ВИРІШЕННЯ ЗАДАЧІ АВТОНОМНОГО ПРОХОДЖЕННЯ ЛАБІРИНТУ У статті розглянуто застосування методу коеволюції для вирішення задачі пошуку виходу зі складного лабіринту автономним агентом, що керується штучною нейронною мережею (ШНМ). Вирішення цієї задачі висвітлює фундаментальну проблему, яка перешкоджає алгоритмічній оптимізації – тісне поєд- нання цілі завдання із цільовою функцією, що використовується для пошуку оптимального рішення. Для вирішення цієї задачі ціль є очевидною – знаходження оптимального шляху крізь лабіринт. У той же час, з цільовою функцією все дещо складніше. В складних конфігураціях лабіринту зазвичай налі- чується багато оманливих зон, які наближені до точки виходу з лабіринту, але є глухими кутами, що не мають шляху до виходу. Таким чином, проста цільова функція, заснована тільки на вимірюванні відстані до виходу з лабіринту, має багато локальних оптимумів в оманливому просторі пошуку рі- шення. З підвищенням складності конфігурації лабіринту, проста цільова функція рано чи пізно за- стряє у одному з локальних оптимумів, що унеможливлює вирішення задачі навігації. Для вирішення цієї проблеми було запропоновано використання стратегії коеволюції популяції аген- тів-вирішувачів та популяції кандидатів у цільові функції. На відміну від попередніх робіт у цьому напрямку, було запропоновано використання алгоритму NEAT для керування процесом коеволюції обох популяцій. Водночас для оптимізації пошуку у просторі рішень було запропоновано викорис- тання методу Novelty Search (NS), який полягає у наданні переваги найбільш інноваційним рішенням. Було наведено опис математичного апарату для визначення шаблону цільової функції, що включає у себе як значення інноваційності рішення, так і значення відстані до виходу з лабіринту. Цей шаблон був взятий за основу при визначенні генному організмів – кандидатів у цільові функції. Для порівняння з попередніми роботами було проведено експеримент для визначення ефективності запропонованого методу коеволюції у вирішенні задачі навігації у складному лабіринті. Ключові слова: генетичні алгоритми, нейроеволюція наростаючих топологій, автономне проходження лабіринту, NEAT, коеволюція. Ia.V. Omelianenko, A.Yu. Doroshenko, Ye.S. Rodin APPLICATION OF COEVOLUTION STRATEGY TO SOLVE THE PROBLEM OF AUTONOMOUS NAVIGATION TROUGH THE MAZE This study explores the use of coevolutionary methods to address the challenge of navigating through complex mazes using autonomous agents controlled by artificial neural networks (ANNs). It underscores a critical impediment to algorithmic optimization: the close interdependence between the task's goal and the objective function used for optimal solution discovery. The task's goal is clear—identify the most efficient route through the maze. However, the objective function's formulation is more complex. In complex maze layouts, numerous deceptive areas may appear proximate to the exit but culminate in dead ends. Consequently, an elementary objective function that merely gauges the proximity to the exit can encounter numerous local optima within this deceptive search space, hindering the search for optimal solution. As maze complexity increases, such an objective function inevitably becomes ensnared in a local optimum, rendering the navigation issue unsolvable. To counteract this, the study proposes a coevolution strategy involving a population of decision-making agents and a population of objective function candidates. This approach diverges from prior research by incorporating the NEAT algorithm to steer the coevolution of both populations. Additionally, the Novelty Search (NS) method was suggested to optimize the search within the potential solution space, favoring the most novel solutions. The paper details the mathematical framework for crafting the objective function template, which integrates the novelty value of the discovered solution and its distance from the maze's exit. This framework serves as the foundation for defining the genomes of the organisms — candidates for the objective functions. For comparison with preceding works, an experiment was conducted to evaluate the efficacy of the proposed coevolution method in resolving the problem of navigation within a complex maze environment. Keywords: genetic algorithms, neuroevolution of augmenting topologies, autonomous maze navigation, NEAT, coevolution © Я.В. Омельяненко, А.Ю. Дорошенко, Є.С. Родін, 2024 ISSN 1727-4907. Проблеми програмування. 2024. №2-3 264 Машинне навчання та нейронні мережі Вступ Застосування будь-якого еволю- ційного алгоритму (ЕА) для навігації у складному середовищі зводиться до вирі- шення задачі пошуку оптимального шляху для досягнення заданої мети. Це, у свою чергу, базується на визначенні ці- льової функції (функції пристосованості), яку ми бажаємо мінімізувати або максимі- зувати. У попередній роботі [1, 2] було по- казано, що існує фундаментальна про- блема, яка виникає на практиці. У той час, як ціль завдання може бути чітко визна- чена та добре відома, цільова функція може бути оманливою. Це можна наочно проілюструвати на прикладі побудови моделі автономного аге- нта для проходження двовимірного лабіри- нту, зображеного на Рис. 1. Завданням кон- тролюючої моделі є керування роботом та- ким чином, щоб за визначену кількість кро- ків він міг пройти лабіринт з початкового положення до виходу. Контролююча мо- дель водночас визначає поведінку робота (напрямок руху) на кожному кроці, залежно від поточного стану середовища: позиція у лабіринті, відстань до стін. Інтуїтивно можливо визначити ціле- орієнтовану функцію як функцію відстані між поточною позицією робота у лабіринті та виходом з нього, як було зроблено у [1]. Але, у складній конфігурації лабіринту агент-вирішувач може зіткнутися з нарос- таючою складністю вибору адекватного напрямку руху на основі відстані до ви- ходу. Як показано на Рис. 1, навіть, якщо відстань до виходу здається мінімальною, це не означає, що шлях до виходу знайдено. Функція пристосованості може мати лока- льні оптимуми у глухих кутах лабіринту, де реєструються круті градієнти значень пока- зників пристосованості (fitness score) [3, 4]. Отож, ми маємо оманливий ландшафт по- казників пристосованості, який не може бути вирішений за допомогою цілеорієнто- ваної функції пристосованості (goal- oriented fitness function). Таким чином, можна зазначити, що навіть, якщо оптимальне рішення може бути визначене контролюючою моделлю, воно не завжди буде знайдене в процесі еволюції, використовуючи просту цільову функцію. Ба більше, наше інтуїтивне визна- чення функції пристосованості здається хи- бним, адже воно ототожнює кінцеву мету (вихід) та дизайн цільової функції (відстань до виходу). Рис. 1. Двовимірний лабіринт з локально оптимальними глухими кутами (затемнені). Для розв’язання цієї проблеми у [5] було запропоновано розділити оптиміза- цію контролюючої моделі та оптимізацію цільової функції, використовуючи метод SAFE (Solution And Fitness Evolution). Ін- шими словами, навіть, якщо метою аге- нта-вирішувача є досягнення точки ви- ходу з лабіринту, це не обов’язково озна- чає, що цільовою функцією є відстань до виходу. Таким чином, пропонується вико- ристовувати метод коеволюції двох попу- ляцій організмів – популяції контролюю- чих моделей та популяції кандидатів у ці- льові функції. Новизна підходу, розглянутого у цій роботі, полягає у використанні алгоритму нейроеволюції NEAT [2, 6, 7, 9] для еволю- ції популяції контролюючих моделей. У даній роботі будуть розглянуті принципи та існуючі типи коєволюції попу- ляцій організмів. Після цього буде запропо- новано метод побудови коеволюційного процесу на основі алгоритму NEAT для на- вчання контролюючих моделей та алгори- тму NEAT, що поєднаний з пошуковою оп- 265 Машинне навчання та нейронні мережі тимізацією методом NS для визначення оп- тимальної цільової функції. Розглянутий метод коєволюції до- зволяє вирішувати задачу оптимальної на- вігації у складному середовищі та вирішу- вати завдання навчання Штучних Нейрон- них Мереж (ШНМ), здатних контролю- вати поведінку автономних роботизова- них агентів. 1. Огляд аналогів Оптимальна навігація у складному оточенні – важлива задача для побудови ав- тономних агентів. Вирішенню цієї задачі присвячено низку наукових досліджень. У [1] було запропоновано викорис- тання алгоритму NEAT із простою цільо- вою функцією, визначеною як відстань між поточною позицією агента та кінцевою ме- тою (вихід з лабіринту). Цей підхід добре працює для простих конфігурацій лабіри- нту, але стикається з труднощами у процесі розв’язання складніших конфігурацій. Для вирішення задачі побудови оп- тимальних контролюючих моделей, здат- них розв’язувати складні конфігурації ла- біринту у [3, 4, 8] було запропоновано ме- тод оптимізації під назвою Novelty Search (NS). Згідно із цим методом, оптимізація еволюційного процесу відбувається так, щоб найбільшу винагороду отримували ор- ганізми, які знайшли більш нове рішення у просторі вже знайдених рішень. Таким чи- ном, цільова функція задається як фактор новизни, а не відстань до мети. Головним рушієм цього методу є натуральна необме- жена еволюція, яка також у багатьох випа- дках оптимізує геном організмів, викорис- товуючи нові комбінації для максималь- ного поширення на невідомі території і по- шук нових поведінкових моделей. Цей ме- тод має цілий ряд переваг, таких як - необ- межений простір пошуку і можливість зна- ходження нетривіального рішення. Крім того, пошук новизни заради самої новизни не дає стимулу для контролюючої моделі, що наблизилась до мети, залишатися на цій траєкторії та покращувати результати. Ба більше, з ускладненням конфігурації лабі- ринту, час потрібний на розв’язання задачі навігації методом NS, може бути досить значним, що робить використання цього методу непрактичним у більшості випадків. На відміну від зазначених вище ме- тодів оптимізації пошуку оптимального рі- шення, запропонований у цій роботі метод коеволюції популяції агентів-вирішувачів та популяції кандидатів у цільові функції, дозволяє знаходити оптимальні рішення за- дачі навігації у складних конфігураціях ла- біринту за прийнятний проміжок часу. Крім того, використання алгоритму NEAT для керування еволюцією агентів-вирішувачів дає змогу отримувати оптимальні топології ШНМ контролюючих моделей. Це робить їх енергоефективними та уможливлює їх використання у системах з обмеженими об- числювальними та енергетичними можли- востями, такими, як промислові роботи, ав- тономні дрони і таке інше. Новизна методу, розглянутого у да- ній роботі, полягає у поєднані алгоритму NEAT для еволюції популяції агентів-вирі- шувачів (контролюючих моделей) та алго- ритму NEAT з пошуковою оптимізацією на основі методу NS (пошук новизни) для ево- люції популяції кандидатів у цільові функ- ції. Крім того, ця робота представляє нову модифікацію методу NS, спрямовану на об- меження простору пошуку для підвищення продуктивності. У статті наведені основні програмні модулі для реалізації методу коеволюції на мові програмування GO. У наступному розділі ми розглянемо основні особливості коеволюції. 2. Особливості коеволюції Природна еволюція біологічних сис- тем не може розглядатися окремо від кон- цепції коеволюції. Коеволюція є однією з основних рушійних сил еволюції, від якої залежить поточний стан біосфери та різно- манітність організмів. Ми можемо визначити коеволюцію як взаємовигідну стратегію одночасної ево- люції безлічі генеалогій різних організмів. Водночас, еволюція одного виду немож- лива без інших. У ході еволюції спільно еволюціонуючі види взаємодіють один з одним, і ці міжвидові відносини формують 266 Машинне навчання та нейронні мережі їхню еволюційну стратегію. Існує три осно- вних типи коеволюції: − мутуалізм, коли два або більше види мирно співіснують та отримують вза- ємну вигоду один від одного; − конкурентна коеволюція: хижацтво, коли один організм уби- ває інший і споживає його ресурси; паразитизм, коли один організм ви- користовує ресурси іншого, але не вбиває його; − комменсалізм, коли представ- ники одного виду отримують вигоду, не за- вдаючи шкоди та не приносячи вигоди ін- шим видам. Останній тип коеволюційної страте- гії привернув увагу дослідників [5] як бага- тообіцяючий для створення ефективного методу навчання автономних агентів. Од- ночасно, було запропоновано реалізацію алгоритму SAFE, який ми розглянемо далі. 3. Особливості алгоритму SAFE Як випливає з назви, метод коеволю- ції вирішувача та пристосованості заснова- ний на спільній еволюції рішення та функ- ції пристосованості, котра спрямовує опти- мізацію пошуку рішення. Метод SAFE створений навколо стратегії коменсалісти- чної коеволюції двох популяцій: − популяція потенційних рішень, які розвиваються, щоб вирішити безпосере- дньо поставлене завдання; − популяція кандидатів на цільові функції, які еволюціонують, щоб спрямову- вати еволюцію популяції рішень. Основна ідея алгоритму SAFE поля- гає в тому, щоб отримати вигоду з викори- стання різних методів оптимізації пошуку для кожної з згаданих популяцій окремо. У даній роботі запропоновано вико- ристання алгоритму NEAT для керування еволюцією популяції потенційних рішень та його поєднання з NS (пошук новизни) для оптимізації еволюційного процесу у по- пуляції кандидатів на цільові функції. Далі ми розглянемо модифікований експеримент з лабіринтом, який буде вико- ристано для оцінки ефективності запропо- нованого рішення. 4. Модифікований експеримент із лабіринтом У [1] було наведено реалізацію кла- сичної задачі з проходження лабіринту, ви- користовуючи алгоритм NEAT для керу- вання еволюційним процесом. Для оптимі- зації пошуку використовувалась проста ці- льова функція, заснована на відстані від по- точного положення агенту-вирішувача до виходу з лабіринту. У цій роботі були використані за- соби, які вже були реалізовані в [1] з пев- ними змінами, необхідними для реалізації методу коеволюції. Головною відмінністю від поперед- ньої праці є визначення функцій пристосо- ваності для обох коеволюційних популяцій та їх відповідна реалізація. Таким чином, нам потрібно визначити дві функції присто- сованості: одну - для кандидатів на вирішу- вачі лабіринтів та іншу - для кандидатів на цільові функції. Тут ми розглянемо обидва варіанти. 5. Функція пристосованості для агенту-вирішувача В кожному поколінні еволюції ко- жен індивідуум (вирішувач лабіринту) оці- нюється всіма кандидатами на цільові фун- кції з іншої коменсалістичної популяції. Ми використовуємо максимальну оцінку прис- тосованості, отриману під час оцінювання кожного окремого агенту-вирішувача кож- ним кандидатом на цільову функцію, як оцінку пристосованості знайденого рі- шення. Функція пристосованості вирішу- вача лабіринту являє собою сукупність двох метрик - відстані від виходу з лабіри- нту (оцінка близькості до мети) і новизни кінцевої позиції вирішувача (оцінка нови- зни). Ці оцінки арифметично поєднуються з використанням пари коефіцієнтів, отри- маних як вихідні дані від конкретного інди- відуума в популяції кандидатів на цільову функцію. Наступна формула дає комбінацію цих показників для оцінки пристосовано- сті: 267 Машинне навчання та нейронні мережі 𝑂𝑂𝑖𝑖(𝑆𝑆𝑖𝑖) = 𝑎𝑎 × 1 𝐷𝐷𝑖𝑖 + 𝑏𝑏 × 𝑁𝑁𝑆𝑆𝑖𝑖 , (1) Тут 𝑂𝑂𝑖𝑖(𝑆𝑆𝑖𝑖) – це значення пристосова- ності, отримані шляхом оцінки кандидата рішення 𝑆𝑆𝑖𝑖, щодо цільової функції 𝑂𝑂𝑖𝑖. Пара коефіцієнтів [a, b] - це вихід конкретного кандидата на цільову функцію. Ця пара ви- значає, якою мірою відстань до виходу з ла- біринту (𝐷𝐷𝑖𝑖) і поведінкова новизна (𝑁𝑁𝑆𝑆𝑖𝑖) рі- шення впливають на кінцеву оцінку прис- тосованості вирішувача лабіринту в кінці траєкторії. Відстань до виходу з лабіринту (𝐷𝐷𝑖𝑖) визначається як евклідова відстань між останніми координатами вирішувача лабі- ринту в його траєкторії та координатами виходу з лабіринту. Відстань обчислюється за такою формулою: 𝐷𝐷𝑖𝑖 = √∑ (𝑎𝑎𝑖𝑖 − 𝑏𝑏𝑖𝑖)22 𝑖𝑖=1 , (2) Де a – координати кінцевої позиції агенту та b – координати виходу з лабіри- нту. Оцінка новизни 𝑁𝑁𝑆𝑆𝑖𝑖 кожного аге- нту-вирішувача лабіринту визначається його остаточним положенням в лабіринті (точка 𝑥𝑥). Вона розраховується як середня відстань від цієї точки до k-найближчих су- сідніх точок, які є остаточними позиціями інших вирішувачів лабіринтів. Наступна формула дає значення оці- нки новизни в точці x поведінкового прос- тору: 𝑁𝑁𝑆𝑆𝑖𝑖 = 1 𝑘𝑘 ∑ 𝑑𝑑𝑖𝑖𝑖𝑖𝑖𝑖(𝑥𝑥,𝑖𝑖)𝑘𝑘 𝑖𝑖=0 , (3) Де 𝑖𝑖 – це i-й найближчий сусід 𝑥𝑥, а 𝑑𝑑𝑖𝑖𝑖𝑖𝑖𝑖(𝑥𝑥,𝑖𝑖) – відстань між 𝑥𝑥 та 𝑖𝑖. Відстань між двома точками є мет- рикою новизни, що вимірює, наскільки по- точне рішення (𝑥𝑥) відрізняється від іншого (𝑖𝑖), створеного різними вирішувачами ла- біринтів. Показник новизни розраховується як евклідова відстань між двома точками: 𝑑𝑑𝑖𝑖𝑖𝑖𝑖𝑖(𝑥𝑥,) = √∑ (𝑥𝑥𝑗𝑗 − 𝑗𝑗) 22 𝑗𝑗=1 , (4) Тут 𝑗𝑗 і 𝑥𝑥𝑗𝑗 – значення позиції j коор- динатних векторів, що містять ко-ординати точок  і 𝑥𝑥 відповідно. Далі ми обговоримо, як визначити функцію адаптації для оптимізації кандида- тів на роль цільової функції. 6. Функція пристосованості для кандидатів на цільову функцію Метод SAFE заснований на коменса- лістичному коеволюційному підході, який означає, що одна зі спільно еволюціоную- чих популяцій не отримує ні користі, ні шкоди в ході еволюції. У експерименті ком- менсалістична популяція є сукупністю кан- дидатів на цільові функції. Для цієї сукуп- ності нам необхідно визначити таку функ- цію пристосованості, яка залежить від яко- сті роботи агентів-вирішувачів лабіринту (контролюючих моделей). Придатним варіантом тут є цільова функція пристосованості, яка для оцінки пристосованості використовує показник новизни. Формула для розрахунку оцінки новизни кожного кандидата на роль цільо- вої функції така ж сама, як і для агентів-ви- рішувачів лабіринтів (3). Єдина відмінність полягає в тому, що у випадку кандидатів на роль цільової функції ми розраховуємо оці- нку новизни, використовуючи вектори з ви- хідними значеннями кожного індивідуума у популяції. Після цього застосовуємо зна- чення показника новизни як показника при- стосованості організму. У [3, 4, 8] наведено реалізацію ме- тоду оптимізації пошуку NS, в який ми ви- мушено внесли модифікації для обмеження простору пошуку. Це зроблено, щоб підви- щити продуктивність алгоритму та гаран- тувати його виконання у заданий проміжок часу. 7. Середовище моделювання задачі лабіринту У рамках цієї роботи було розроб- лене програмне забезпечення для моделю- вання задачі проходження лабіринту схоже до наведеного у [1], але використовуючи мову програмування GO з відповідними змінами для організації коеволюції двох по- 268 Машинне навчання та нейронні мережі пуляцій. Воно складається з таких основ- них компонентів, які реалізовані у вигляді окремих класів: − Agent – клас, який зберігає інфо- рмацію, пов'язану з агентом навігатора ла- біринту, задіяного в симуляції. − RecordStore - клас, який управляє зберіганням записів, що належить до оці- нок усіх вирішальних агентів в ході еволю- ційного процесу. Зібрані записи можна ви- користовувати для аналізу еволюційного процесу після його завершення. − Environment – клас, який містить інформацію про середовище моделювання лабіринту. Цей клас також надає методи, які керують середовищем моделювання, керу- ють положенням вирішального агенту, ви- являють зіткнення зі стінами лабіринту та генерують вхідні дані для датчиків агента. − NoveltyItem – клас, для інкапсу- ляції інформації про певний елемент, який містить інформацію про оцінку новизни, пов’язану з певним геномом, разом із допо- міжною інформацією. Він використову- ється в поєднанні з NoveltyArchive − NoveltyArchive – клас, який управляє збереженням усіх знайдених NoveltyItem та надає можливість для оцінки їх новизни в міру знаходження нових точок. Далі ми розглянемо деталі проведе- ного експерименту. 8. Експеримент із складною конфігурацією лабіринту У цій роботі було проведено дослі- дження з метою побудови контролюючої моделі, яка здатна вирішити задачу навігації у складному лабіринті, схема якого наведена на Рис. 1. Це дозволяє порівняти метод кое- волюції з методом простої еволюції, що на- ведений у попередній роботі [1]. За резуль- татами уієї роботи було показано, що прос- тий еволюційний процес, керуючись алго- ритмом NEAT, може вирішити задачу наві- гації в простому лабіринті, але стикається з труднощами у застосуванні його до складні- ших конфігурацій лабіринту. Тому цей екс- перимент є показовим для доведення ефек- тивності застосування методу коеволюції. Лабіринт має дві фіксовані позиції, відзначені забарвленими кругами. Нижній лівий круг позначає початкову позицію аге- нта-вирішувача лабіринту. Верхній лівий круг позначає точне місце виходу з лабіри- нту, яке повинно бути знайдене. Щоб вико- нати завдання, робот повинен досягти то- чки поблизу виходу з лабіринту. 9. Результати експерименту Експеримент був проведений з вико- ристанням мови програмування GO версії 1.24.1 та бібліотек goNEAT версії 4.0.2 [10], goNEAT_NS версії 4.0.2 [11]. Робоча стан- ція, що використовувалась для цього, має наступні параметри: CPU 2,3 GHz 8-Core Intel Core i9, 16 GB 2667 MHz DDR4, macos 14.4.1. Успішний агент-вирішувач був знайдений після 211 поколінь еволюції та має наступну конфігурацію - 22 вузли поєд- нані 47 зв’язками. У процесі коеволюції також були знайдені оптимальні коефіцієнти [a, b] ці- льової функції, яка була використана для навчання успішного агента-вирішувача: [- 0.53283, 0.95889]. Таким чином, формулу (1) можна переписати, підставивши знай- дені коефіцієнти: 𝑂𝑂𝑖𝑖(𝑆𝑆𝑖𝑖) = −0.53 × 1 𝐷𝐷𝑖𝑖 + 0.96 × 𝑁𝑁𝑆𝑆𝑖𝑖, (5) Згідно з формулою (5) можна зро- бити висновки, що знайдена цільова функ- ція акцентує навчання на пошуку найбільш інноваційних рішень (𝑁𝑁𝑆𝑆𝑖𝑖), приділяючи менше уваги значенню відстані до виходу з лабіринту (𝐷𝐷𝑖𝑖). Це підтверджує тезу, наве- дену на початку цієї роботи про те, що у складному оточенні успішна цільова функ- ція не тотожна відстані до мети (виходу з лабіринту). Рис. 2. Шлях успішного агента-вирішувача (знизу – початок, зверху – вихід). 269 Машинне навчання та нейронні мережі Доречним буде розглянути візуалі- зацію проходження лабіринту успішним агентом-вирішувачем (Рис. 2), звертаючи увагу на плавність та наближеність до оп- тимального знайденого маршруту. Рис. 3. Візуалізація оцінки популяції орга- нізмів для агентів-вирішувачів. Крім того, на Рис. 3 можна побачити, що протягом усіх епох еволюції тільки один вид організмів з наявних 46 породив конфігурацію контролюючої ШНМ успіш- ного агента-вирішувача. На цьому рисунку ми також бачимо, що більшість еволюцій- них невдах застрягло у локальних оптиму- мах. Водночас, успішний агент виявив най- більшу інноваційність, надаючи перевагу дослідженню нових ділянок, на противагу використанню вже відомих (exploration vs exploitation). Висновки У роботі показано, як метод коево- люції двох популяцій – популяції агентів- вирішувачів та популяції у кандидати на ці- льову функцію може бути використано для розв’язання задачі навігації у складному ла- біринті. Експериментально доведено, що цей метод є ефективнішим за метод розгля- нутий у [1]. Порівняно з попередніми роботами [5], було запропоновано новий підхід до ре- алізації методу коеволюції SAFE (Solution and Fitness Coevolution), який полягає у за- стосуванні алгоритму NEAT для керування еволюційним процесом двох популяцій, об’єднанних коменсалістичною коеволю- цією. Водночас для оптимізації пошуку рі- шень у оманливому середовищі потенцій- них рішень було застосовано метод Novelty Search (пошук новизни). Було створено програмне забезпе- чення для проведення експерименту з кое- волюції мовою програмування GO. Крім того, були використанні передові засоби ві- зуалізації, які дозволяють наочно оціню- вати результати коеволюції зі зміною вхід- них параметрів. References 1. Iaroslav Omelianenko. 2023. Simulation of the autonomous maze navigation using the NEAT algorithm. Problems in programming 4, (2023), 76-89. DOI: 10.15407/pp2023.04.076 2. Iaroslav Omelianenko. Hands-On Neuroevolu- tion with Python: Build high-performing artifi- cial neural network architectures using neuro- evolution-based algorithms. Birmingham, UK: Packt Publishing Ltd, 2019. ISBN: 9781838824914, 368 pp. 3. Joel Lehman and Kenneth O Stanley. 2010. Revising the evolutionary computation ab- straction: minimal criteria novelty search. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2010). ACM, 103–110. 4. Joel Lehman and Kenneth O Stanley. 2011. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary compu- tation 19, 2 (2011), 189–223. 5. M. Sipper, J. H. Moore and R. J. Urbanowicz, "Solution and Fitness Evolution (SAFE): A Study of Multiobjective Problems," 2019 IEEE Congress on Evolutionary Computation (CEC), Wellington, New Zealand, 2019, pp. 1868-1874, doi: 10.1109/CEC.2019.8790274. 6. Kenneth O Stanley and Risto Miikkulainen. 2002. Evolving neural networks through aug- menting topologies. Evolutionary computation 10, 2 (2002), 99–127. 7. Сініцин І.П., Дорошенко А.Ю., Мамедов Т.А., Яценко О.А. Метод автоматизованого проєктування нейроеволюційних алгоритмів з використанням алгебри алгоритмів Глушкова. Проблеми керування та інформатики, 2023, №3. С.74-85. https://doi.org/10.34229/1028-0979-2023-3-8 8. Iaroslav Omelianenko. Creation of Autono- mous Artificial Intelligent Agents Using Nov- elty Search Method of Fitness Function Opti- 270 Машинне навчання та нейронні мережі mization. NewGround LLC, Sept. 2018, https://hal.science/hal-01868756. 9. Iaroslav Omelianenko. “Autonomous Artifi- cial Intelligent Agents”. In: Machine Learning and the City. John Wiley Sons, Ltd, 2022. Chap. 12, pp. 263–285. ISBN: 9781119815075, DOI: 10.1002/9781119815075.ch21, URL: https://onlineli- brary.wiley.com/doi/abs/10.1002/9781119815 075.ch21, SCOPUS: 2-s2.0-85147956837, https://www.scopus.com/record/dis- play.uri?eid=2-s2.0-85147956837&origin=in- ward&txGid=b119d677e846feb8f319ba241f7 59c75 10. Omelianenko, Iaroslav (2023). The GoLang implementation of NeuroEvolution of Aug- menting Topologies (NEAT) algorithm (v4.0.2). [Computer software]. Zenodo. https://doi.org/10.5281/zenodo.10119451 11. Omelianenko, Iaroslav (2024). The GOLang implementation of NeuroEvolution of Augmenting Topologies (NEAT) with Novelty Search optimization (v4.0.2). [Computer soft- ware]. Zenodo. https://doi.org/10.5281/zenodo.10951521 Одержано: 12.04.2024 Внутрішня рецензія отримана: 20.04.2024 Зовнішня рецензія отримана: 27.04.2024 Про авторів: 1Омельяненко Ярослав Вікторович, аспірант, молодший науковий співробітник https://orcid.org/0000-0002-2190-5664 1,2Дорошенко Анатолій Юхимович, доктор фізико-математичних наук, професор, завідувач відділу теорії комп'ютерних обчислень http://orcid.org/0000-0002-8435-1451 1Родін Євген Сергійович, молодший науковий співробітник https://orcid.org/0000-0003-2416-8572 Місце роботи авторів: 1ІПС НАН України, 03187, м. Київ-187, проспект Академіка Глушкова, 40. E-mail: yaric@newground.com.ua Сайт: www.iss.nas.gov.ua 2НТУУ «КПІ імені Ігоря Сікорського». м. Київ, проспект Перемоги 37.

Application of coevolution strategy to solve the problem of autonomous navigation trough the maze

Institution

Ähnliche Einträge