Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Sapunov S. V. Reconstruction of a Labeled Graph by a Graph-walking Mobile Agent. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2015, vol. 15, iss. 2, pp. 228-238. DOI: 10.18500/1816-9791-2015-15-2-228-238, EDN: TXMFUP

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
11.06.2015
Full text:
download
(downloads: 170)
Language: 
Russian
Heading: 
Computer Sciences
UDC: 
519.7
DOI: 
10.18500/1816-9791-2015-15-2-228-238
EDN: 
TXMFUP

Reconstruction of a Labeled Graph by a Graph-walking Mobile Agent

Autors: 
Sapunov Sergey Valerievich, Institute of Applied Mathematics and Mechanics
Abstract: 

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.

Key words: 
vertex labeled graphs
mobile agent
graph reconstruction
References: 
  1. Letichevsky A. Algebra of behavior transformation and its application // Structural Theory of Automata, Semigroups and Universal Algebra. Springer, 2005. P. 241–272.
  2. Droste M., Kuich W., Vogler H. Handbook of Weighted Automata. Springer, 2009. 608 p.
  3. Dudek G., Jenkin M. Computational Principles of Mobile Robotics. Cambridge : Cambridge Univ. Press, 2010. 406 p.
  4. Baier C., Katoen J.-P. Principle of Model Checking. MIT Press, 2008. 984 p.
  5. Капитонова Ю. В., Летичевский А. А. Математическая теория проектирования вычислительных систем. М. : Наука, 1988. 298 с.
  6. Голубев Д. В. Об обходе графов автоматами с одной нестираемой краской // Интеллектуальные системы. 1999. Т. 4, вып. 1–2. С. 243–272.
  7. Грунский И. С., Сапунов С. В. Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации // Искусственный интеллект. 2012. № 4. С. 420–428.
  8. Грунский И. С., Сапунов С. В. Идентификация вершин помеченных графов // Труды ИПММ НАНУ. 2010. Т. 21. С. 86–97.
  9. Грунский И. С., Сапунов С. В. Диагностика местоположения мобильного робота на основе топологической информации о среде // Искусственный интеллект. 2011. № 2. С. 15–25.
  10. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы : построение и анализ. М. : МЦНМО, 2001. 960 с.
Received: 
12.01.2015
Accepted: 
26.05.2015
Published: 
30.06.2015
  • 853 reads