Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem)
We continue our study of multiagent algorithms for a problem that we call the Mars Robot Puzzle. This problem could be considered as a special case of a graph-theoretic problem (Discrete Mathematics), as a combinatorial geometry problem (Computer Science), or as a very special case of a path-planni...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2011-06-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1091 |
| _version_ | 1797877942622093312 |
|---|---|
| author | E. V. Bodin N. O. Garanina N. V. Shilov |
| author_facet | E. V. Bodin N. O. Garanina N. V. Shilov |
| author_sort | E. V. Bodin |
| collection | DOAJ |
| description | We continue our study of multiagent algorithms for a problem that we call the Mars Robot Puzzle. This problem could be considered as a special case of a graph-theoretic problem (Discrete Mathematics), as a combinatorial geometry problem (Computer Science), or as a very special case of a path-planning problem (Artificial Intelligence). Our algorithms grew up from a local search (heuristic) solution of the problem suggested by E.W. Dijkstra. In the paper we present a series of new multiagent algorithms solving the problem, prove (manually) their correctness, model check some of these algorithms, and discuss further research topics. All our algorithms are multiagent in contrast to "centralized" graph and combinatorial algoritms; correctness of our algorithms is formally proven, while the testing is used for validation of path-planning algorithms. |
| first_indexed | 2024-04-10T02:24:46Z |
| format | Article |
| id | doaj.art-4c60c0eed5cc4e9fbaeedddaf6455e60 |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-10T02:24:46Z |
| publishDate | 2011-06-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-4c60c0eed5cc4e9fbaeedddaf6455e602023-03-13T08:07:31ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172011-06-01182113128832Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem)E. V. Bodin0N. O. Garanina1N. V. Shilov2Институт Систем Информатики им. А.П. Ершова СО РАНИнститут Систем Информатики им. А.П. Ершова СО РАНИнститут Систем Информатики им. А.П. Ершова СО РАНWe continue our study of multiagent algorithms for a problem that we call the Mars Robot Puzzle. This problem could be considered as a special case of a graph-theoretic problem (Discrete Mathematics), as a combinatorial geometry problem (Computer Science), or as a very special case of a path-planning problem (Artificial Intelligence). Our algorithms grew up from a local search (heuristic) solution of the problem suggested by E.W. Dijkstra. In the paper we present a series of new multiagent algorithms solving the problem, prove (manually) their correctness, model check some of these algorithms, and discuss further research topics. All our algorithms are multiagent in contrast to "centralized" graph and combinatorial algoritms; correctness of our algorithms is formally proven, while the testing is used for validation of path-planning algorithms.https://www.mais-journal.ru/jour/article/view/1091мультиагентная системараспределённый алгоритмзадача о назначенияхпланирование перемещений |
| spellingShingle | E. V. Bodin N. O. Garanina N. V. Shilov Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem) Моделирование и анализ информационных систем мультиагентная система распределённый алгоритм задача о назначениях планирование перемещений |
| title | Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem) |
| title_full | Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem) |
| title_fullStr | Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem) |
| title_full_unstemmed | Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem) |
| title_short | Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem) |
| title_sort | mars robot puzzle a multiagent approach to the dijkstra problem |
| topic | мультиагентная система распределённый алгоритм задача о назначениях планирование перемещений |
| url | https://www.mais-journal.ru/jour/article/view/1091 |
| work_keys_str_mv | AT evbodin marsrobotpuzzleamultiagentapproachtothedijkstraproblem AT nogaranina marsrobotpuzzleamultiagentapproachtothedijkstraproblem AT nvshilov marsrobotpuzzleamultiagentapproachtothedijkstraproblem |