Geodesic
Mars robot puzzle (a multiagent approach to the Dijkstra problem)
Modelirovanie i analiz informacionnyh sistem, Tome 18 (2011) no. 2, pp. 113-128.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: multiagent system, distributed algorithm, assignment problem, path-planning problem. 
@article{MAIS_2011_18_2_a6,
     author = {E. V. Bodin and N. O. Garanina and N. V. Shilov},
     title = {Mars robot puzzle (a multiagent approach to the {Dijkstra} problem)},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {113--128},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2011_18_2_a6/}
}
TY  - JOUR
AU  - E. V. Bodin
AU  - N. O. Garanina
AU  - N. V. Shilov
TI  - Mars robot puzzle (a multiagent approach to the Dijkstra problem)
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2011
SP  - 113
EP  - 128
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2011_18_2_a6/
LA  - ru
ID  - MAIS_2011_18_2_a6
ER  - 
%0 Journal Article
%A E. V. Bodin
%A N. O. Garanina
%A N. V. Shilov
%T Mars robot puzzle (a multiagent approach to the Dijkstra problem)
%J Modelirovanie i analiz informacionnyh sistem
%D 2011
%P 113-128
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2011_18_2_a6/
%G ru
%F MAIS_2011_18_2_a6
E. V. Bodin; N. O. Garanina; N. V. Shilov. Mars robot puzzle (a multiagent approach to the Dijkstra problem). Modelirovanie i analiz informacionnyh sistem, Tome 18 (2011) no. 2, pp. 113-128. http://geodesic.mathdoc.fr/item/MAIS_2011_18_2_a6/

[1] R. Fagin, J. Y. Halpern, Y. Moses, M. Y. Vardi, Reasoning about Knowledge, MIT Press, London, 1995 | MR | Zbl

[2] N. O. Garanina, N. V. Shilov, L. E. Konyaev, Can Robots Solve the Assignment Problem?, Proc. Int. Workshop on Concurrency, Specification, and Programming, v. 1, Krakow-Przegorzaly, Poland, 2009, 154–163

[3] S. M. LaValle, Planning Algorithms, Cambridge University Press, 2006 | MR | Zbl

[4] N. V. Shilov, N. O. Garanina, “Modal Logics for reasoning about Multiagent Systems”, Encyclopedia of Artificial Intelligence, Information Science Reference, eds. J. R. Rabucal, J. Dorado, A. P. Sierra, 2008, 1089–1094

[5] N. V. Shilov, S. O. Shilova, “Etude on theme of Dijkstra”, ACM SIGACT News, 35:3 (2004), 102–108 | DOI

[6] N. V. Shilov, S. O. Shilova, “On Mathematical Contents of Computer Science Contests”, Proc. the 1st KAIST International Symposium on Enhancing University Mathematics Teaching, Daejeon, Korea, 2005, 223–233

[7] M. Wooldridge, An Introduction to Multiagent Systems, John Willey Sons Ltd, 2002

[8] V. G. Boltyanskii, P. S. Soltan, Kombinatornaya geometriya razlichnykh klassov vypuklykh mnozhestv, Shtiintsa, Kishinev, 1978 | MR

[9] D. Yu. Bugaichenko, I. P. Solovev, “Abstraktnaya arkhitektura intellektualnogo agenta i metody ee realizatsii”, Sistemnoe programmirovanie, SPb, 2005, 36–66

[10] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lektsii po teorii grafov, Nauka, M., 1990 | MR | Zbl

[11] T. Kh. Kormen, I. Ch. Leizerson, R. L. Rivest, K. Shtain, Algoritmy: postroenie i analiz, Vilyams, M., 2006, 1296 pp.

[12] Zh. Tel, Vvedenie v raspredelennye algoritmy, MTsNMO, M., 2009

[13] G. Khadviger, G. Debrunner, Kombinatornaya geometriya ploskosti, Nauka, M., 1965 | MR

[14] D. Cheremisinov, L. Cheremisinova, “Podkhod k programmirovaniyu agentov v multiagentnykh sistemakh”, Information Science and Computing, International Book Series, 4, 2008, 141–147