Geodesic
Reconstruction of a labeled graph by a graph-walking mobile agent
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 15 (2015) no. 2, pp. 228-238 
S. V. Sapunov. Reconstruction of a labeled graph by a graph-walking mobile agent. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 15 (2015) no. 2, pp. 228-238. http://geodesic.mathdoc.fr/item/ISU_2015_15_2_a14/
@article{ISU_2015_15_2_a14,
     author = {S. V. Sapunov},
     title = {Reconstruction of a labeled graph by a graph-walking mobile agent},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {228--238},
     year = {2015},
     volume = {15},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2015_15_2_a14/}
}
TY  - JOUR
AU  - S. V. Sapunov
TI  - Reconstruction of a labeled graph by a graph-walking mobile agent
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2015
SP  - 228
EP  - 238
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/ISU_2015_15_2_a14/
LA  - ru
ID  - ISU_2015_15_2_a14
ER  - 
%0 Journal Article
%A S. V. Sapunov
%T Reconstruction of a labeled graph by a graph-walking mobile agent
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2015
%P 228-238
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/ISU_2015_15_2_a14/
%G ru
%F ISU_2015_15_2_a14

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

The problem of construction of graph-like operational environment by a mobile agent is considered. The model of environment is defined as a simple undirected vertex labeled graph. We propose a polynomial time algorithm of graph reconstruction and labeling for the collective consisting of agent-explorer and agent-supervisor.

[1] Letichevsky A., “Algebra of behavior transformation and its application”, Structural Theory of Automata, Semigroups and Universal Algebra, Springer, 2005, 241–272 | DOI | MR

[2] Droste M., Kuich W., Vogler H., Handbook of Weighted Automata, Springer, 2009, 608 pp. | MR | Zbl

[3] Dudek G., Jenkin M., Computational Principles of Mobile Robotics, Cambridge Univ. Press, Cambridge, 2010, 406 pp. | Zbl

[4] Baier C., Katoen J.-P., Principle of Model Checking, MIT Press, 2008, 984 pp. | MR

[5] Kapitonova Yu. V., Letichevsky A. A., Mathematical Theory of Computational Systems Design, Nauka, M., 1988, 298 pp. (in Russian)

[6] Golubev D. V., “On Graph Traversal by Automata with Single Nonerasable Coloration”, Intelligent systems, 4:1–2 (1999), 243–272 (in Russian) | MR

[7] Grunsky I. S., Sapunov S. V., “Reconstruction of the graph of operating environment of mobile robot by vertex-labeling sufficient for further navigation”, Artificial Intelligence, 2012, no. 4, 420–428

[8] Grunsky I. S., Sapunov S. V., “Vertex Identification on Vertex Labeled Graphs”, Trudy IPMM NANU, 21 (2010), 86–97 (in Russian) | Zbl

[9] Grunsky I. S., Sapunov S. V., “Mobile robot location diagnostics on the basis of topological information about environment”, Artificial Intelligence, 2011, no. 2, 15–25

[10] Cormen T., Leiserson Ch., Rivest R., Algorithms: construction and analysis, MCNMO, M., 2001, 960 pp. (in Russian)