maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State Universitymais-1091Research ArticleОригинальные статьиArticlesЗадача о роботах на Марсе (мультиагентный подход к задаче Дейкстры)Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem)БодинЕвгений ВикторовичBodinE. V.bodin@iis.nsk.suГаранинаНаталья ОлеговнаGaraninaN. O.garanina@iis.nsk.suШиловНиколай ВячеславовичShilovN. V.shilov@iis.nsk.suИнститут Систем Информатики им. А.П. Ершова СО РАНRussian Federation201120062011182113128Copyright © Бодин Е.В., Гаранина Н.О., Шилов Н.В., 20112011Бодин Е.В., Гаранина Н.О., Шилов Н.В.Bodin E.V., Garanina N.O., Shilov N.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1091

Изучаются мультиагентные алгоритмы для так называемой задачи о роботах на Марсе. Эту задачу можно рассматривать как задачу из теории графов (дискретная математика), как комбинаторную геометрическую задачу (теоретическое программирование) или как частный случай задачи планирования перемещений (искусственный интеллект). Наши алгоритмы основаны на эвристическом поиске, предложенном Э. Дейкстрой. В статье представлен ряд новых мультиагентных алгоритмов, решающих задачи о роботах на Марсе, доказана их корректность, приведены результаты проверки на модели некоторых из этих алгоритмов, предложены направления дальнейших исследований. Новизна представленной работы состоит в том, что в отличие от теоретико-графового и комбинаторно-геометрического подходов, ориентированных на централизованное решение задачи, мы развиваем мультиагентный подход, но, в свою очередь, наша работа отличается от работ по планированию перемещений математической строгостью доказательств корректности предложенных алгоритмов. Я, робот. А. Азимов

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.

мультиагентная системараспределённый алгоритмзадача о назначенияхпланирование перемещенийmultiagent systemdistributed algorithmassignment problempath-planning problemReferencesFagin R., Halpern J.Y., Moses Y., Vardi M.Y. Reasoning about Knowledge. London: MIT Press, 1995.Fagin R., Halpern J.Y., Moses Y., Vardi M.Y. Reasoning about Knowledge. London: MIT Press, 1995.Garanina N.O., Shilov N.V., and Konyaev L.E. Can Robots Solve the Assignment Problem? // Proc. Int. Workshop on Concurrency, Specification, and Programming.Krakow-Przegorzaly, Poland, 2009. V. 1. P. 154-163.Garanina N.O., Shilov N.V., and Konyaev L.E. Can Robots Solve the Assignment Problem? // Proc. Int. Workshop on Concurrency, Specification, and Programming.Krakow-Przegorzaly, Poland, 2009. V. 1. P. 154-163.LaValle S.M. Planning Algorithms. Cambridge University Press, 2006.LaValle S.M. Planning Algorithms. Cambridge University Press, 2006.Shilov N.V., Garanina N.O. Modal Logics for reasoning about Multiagent Systems // Encyclopedia of Artificial Intelligence. J.R. Rabucal, J. Dorado, A.P. Sierra, editors. Information Science Reference, 2008. P. 1089-1094.Shilov N.V., Garanina N.O. Modal Logics for reasoning about Multiagent Systems // Encyclopedia of Artificial Intelligence. J.R. Rabucal, J. Dorado, A.P. Sierra, editors. Information Science Reference, 2008. P. 1089-1094.Shilov N.V., Shilova S.O. Etude on theme of Dijkstra // ACM SIGACT News. 2004. V. 35(3). P. 102-108.Shilov N.V., Shilova S.O. Etude on theme of Dijkstra // ACM SIGACT News. 2004. V. 35(3). P. 102-108.Shilov N.V., Shilova S.O. On Mathematical Contents of Computer Science Contests // Proc. the 1st KAIST International Symposium on Enhancing University Mathematics Teaching. Daejeon, Korea, 2005. P. 223-233.Shilov N.V., Shilova S.O. On Mathematical Contents of Computer Science Contests // Proc. the 1st KAIST International Symposium on Enhancing University Mathematics Teaching. Daejeon, Korea, 2005. P. 223-233.Wooldridge M. An Introduction to Multiagent Systems. John Willey & Sons Ltd, 2002.Wooldridge M. An Introduction to Multiagent Systems. John Willey & Sons Ltd, 2002.Болтянский В.Г., Солтан П.С. Комбинаторная геометрия различных классов выпуклых множеств. Кишинев: Штиинца, 1978.Болтянский В.Г., Солтан П.С. Комбинаторная геометрия различных классов выпуклых множеств. Кишинев: Штиинца, 1978.Бугайченко Д.Ю., Соловьев И.П. Абстрактная архитектура интеллектуального агента и методы её реализации // Системное программирование. СПб,2005.С. 36-66.Бугайченко Д.Ю., Соловьев И.П. Абстрактная архитектура интеллектуального агента и методы её реализации // Системное программирование. СПб,2005.С. 36-66.Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.Кормен Т. Х., Лейзерсон И. Ч., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2006. 1296 с.Кормен Т. Х., Лейзерсон И. Ч., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2006. 1296 с.Тель Ж. Введение в распределенные алгоритмы. М.: МЦНМО, 2009.Тель Ж. Введение в распределенные алгоритмы. М.: МЦНМО, 2009.Хадвигер Г., Дебруннер Г. Комбинаторная геометрия плоскости. М.: Наука, 1965.Хадвигер Г., Дебруннер Г. Комбинаторная геометрия плоскости. М.: Наука, 1965.Черемисинов Д., Черемисинова Л. Подход к программированию агентов в мультиагентных системах // International Book Series "Information Science and Computing". 2008. № 4. С. 141-147.Черемисинов Д., Черемисинова Л. Подход к программированию агентов в мультиагентных системах // International Book Series "Information Science and Computing". 2008. № 4. С. 141-147.

The authors declare that there are no conflicts of interest present.