Cite this article as:
Sapunov S. V. Reconstruction of a Labeled Graph by a Graph-walking Mobile Agent. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2015, vol. 15, iss. 2, pp. 228-238. DOI: https://doi.org/10.18500/1816-9791-2015-15-2-228-238
Language:
Russian
Heading:
UDC:
519.7
Reconstruction of a Labeled Graph by a Graph-walking Mobile Agent
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:
References
- Letichevsky A. Algebra of behavior transformation and its application // Structural Theory of Automata, Semigroups and Universal Algebra. Springer, 2005. P. 241–272.
- Droste M., Kuich W., Vogler H. Handbook of Weighted Automata. Springer, 2009. 608 p.
- Dudek G., Jenkin M. Computational Principles of Mobile Robotics. Cambridge : Cambridge Univ. Press, 2010. 406 p.
- Baier C., Katoen J.-P. Principle of Model Checking. MIT Press, 2008. 984 p.
- Капитонова Ю. В., Летичевский А. А. Математическая теория проектирования вычислительных систем. М. : Наука, 1988. 298 с.
- Голубев Д. В. Об обходе графов автоматами с одной нестираемой краской // Интеллектуальные системы. 1999. Т. 4, вып. 1–2. С. 243–272.
- Грунский И. С., Сапунов С. В. Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации // Искусственный интеллект. 2012. № 4. С. 420–428.
- Грунский И. С., Сапунов С. В. Идентификация вершин помеченных графов // Труды ИПММ НАНУ. 2010. Т. 21. С. 86–97.
- Грунский И. С., Сапунов С. В. Диагностика местоположения мобильного робота на основе топологической информации о среде // Искусственный интеллект. 2011. № 2. С. 15–25.
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы : построение и анализ. М. : МЦНМО, 2001. 960 с.
Full text:
89