Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem)
Abstract
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.
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.
About the Authors
E. V. Bodin
Институт Систем Информатики им. А.П. Ершова СО РАН
Russian Federation
Russian Federation
N. O. Garanina
Институт Систем Информатики им. А.П. Ершова СО РАН
Russian Federation
Russian Federation
N. V. Shilov
Институт Систем Информатики им. А.П. Ершова СО РАН
Russian Federation
Russian Federation
References
1. Fagin R., Halpern J.Y., Moses Y., Vardi M.Y. Reasoning about Knowledge. London: MIT Press, 1995.
2. 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.
3. LaValle S.M. Planning Algorithms. Cambridge University Press, 2006.
4. 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.
5. Shilov N.V., Shilova S.O. Etude on theme of Dijkstra // ACM SIGACT News. 2004. V. 35(3). P. 102-108.
6. 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.
7. Wooldridge M. An Introduction to Multiagent Systems. John Willey & Sons Ltd, 2002.
8. Болтянский В.Г., Солтан П.С. Комбинаторная геометрия различных классов выпуклых множеств. Кишинев: Штиинца, 1978.
9. Бугайченко Д.Ю., Соловьев И.П. Абстрактная архитектура интеллектуального агента и методы её реализации // Системное программирование. СПб,2005.С. 36-66.
10. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.
11. Кормен Т. Х., Лейзерсон И. Ч., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2006. 1296 с.
12. Тель Ж. Введение в распределенные алгоритмы. М.: МЦНМО, 2009.
13. Хадвигер Г., Дебруннер Г. Комбинаторная геометрия плоскости. М.: Наука, 1965.
14. Черемисинов Д., Черемисинова Л. Подход к программированию агентов в мультиагентных системах // International Book Series "Information Science and Computing". 2008. № 4. С. 141-147.
Review
For citations:
Bodin E.V., Garanina N.O., Shilov N.V. Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem). Modeling and Analysis of Information Systems. 2011;18(2):113-128. (In Russ.)
Views:
518
Email this article 