Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

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

Для цитирования:

Сапунов С. В. Восстановление графа с помеченными вершинами перемещающимся по нему мобильным агентом // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 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: 225)
Язык публикации: 
русский
Рубрика: 
Информатика
УДК: 
519.7
DOI: 
10.18500/1816-9791-2015-15-2-228-238
EDN: 
TXMFUP

Восстановление графа с помеченными вершинами перемещающимся по нему мобильным агентом

Автор:
Импортов Импорт Импортович
Авторы: 
Сапунов Сергей Валерьевич, Институт прикладной математики и механики НАН Украины, г. Донецк
Аннотация: 

Рассматривается задача построения автономным мобильным агентом топологической модели своей операционной среды. Модель среды представляет собой связный неориентированный граф с помеченными вершинами. В работе предложен полиномиальный алгоритм восстановления и разметки графа среды для коллектива из агента-исполнителя и агента-вычислителя.

Ключевые слова: 
графы с помеченными вершинами
мобильный агент
восстановление графа
Список источников: 
  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 с.
Поступила в редакцию: 
12.01.2015
Принята к публикации: 
26.05.2015
Опубликована: 
30.06.2015
  • 1091 просмотр