Для цитирования:
Сапунов С. В. Восстановление графа с помеченными вершинами перемещающимся по нему мобильным агентом // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2015. Т. 15, вып. 2. С. 228-238. DOI: 10.18500/1816-9791-2015-15-2-228-238, EDN: TXMFUP
Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн:
11.06.2015
Полный текст:
(downloads: 209)
Язык публикации:
русский
Рубрика:
УДК:
519.7
EDN:
TXMFUP
Восстановление графа с помеченными вершинами перемещающимся по нему мобильным агентом
Авторы:
Сапунов Сергей Валерьевич, Институт прикладной математики и механики НАН Украины, г. Донецк
Аннотация:
Рассматривается задача построения автономным мобильным агентом топологической модели своей операционной среды. Модель среды представляет собой связный неориентированный граф с помеченными вершинами. В работе предложен полиномиальный алгоритм восстановления и разметки графа среды для коллектива из агента-исполнителя и агента-вычислителя.
Ключевые слова:
Список источников:
- 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 с.
Поступила в редакцию:
12.01.2015
Принята к публикации:
26.05.2015
Опубликована:
30.06.2015
- 1033 просмотра