Задача прохождения лабиринта интеллектуальными агентами

Ассматривается задача прохождения лабиринта автоматами. Дается краткий обзор работ, посвященных поведению конечных автоматов в шахматных лабиринтах. Обсуждаются особенности постановок задачи обхода лабиринтов интеллектуальными агентами. Анализируется архитектура интеллектуальных агентов, способных распознавать лабиринт и планировать процессы поиска. Предложена формальная схема ситуационного моделирования поведения интеллектуальных агентов. Обсуждаются вопросы оптимизации маршрутов движения в лабиринте.

шахматный лабиринт, поведение автоматов, интеллектуальные агенты, архитектура, ситуационная модель поведения, планирование действий, оптимизация маршрутов, chess maze, automata conduct, intelligent agents, architecture, the situating model of conduct, planning of actions, optimization of routes

1. Кудрявцев В. Б., Килибарда Г., Ушчумлич Ш. М. О поведении автоматов в лабиринтах // Дискретная математика. 1992. Т. 4, Вып. 3. С. 3-28.

2. Кудрявцев В. Б., Килибарда Г., Ушчумлич Ш. М. Независимые системы автоматов в лабиринтах // Дискретная математика. 2003. Т. 15, Вып. 2. С. 3-39.

3. Килибарда Г., Кудрявцев В. Б., Ушчумлич Ш. М. Коллективы автоматов в лабиринтах // Дискретная математика. 2003. Т. 15, Вып. 3. С. 3-39.

4. Кудpявцев В. Б., Килибарда Г., Ушчумлич Ш. М. Системы автоматов в лабиринтах // Интеллектуальные системы. 2006. Т. 10, Вып. 1-4. C. 449-562.

5. Мартыненко Ю. Г. Динамика мобильных роботов // Соро-совский образовательный журнал. 2000. Т. 6, № 5. С. 110-116.

6. Micromouse - конкурс для маленьких роботов. URL: https://geektimes.ru/post/133577/.

7. Рейнер П. Роботы, лабиринты и архитектура поглощения. URL: http://pandia.ru/text/79/049/45546.php.

8. Shannon Cl. E. Presentation of a Maze-Solving Machine // Cybernetics Trans. of the 8th Conf. of the Josiah Macy Jr. Found / Editor: H. Forester, 1951. P. 173-180.

9. Гарднер М. Математические головоломки и развлечения. М.: Мир, 1999. 447 с.

10. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. 368 с.

11. Freeman H. On the Encoding of Arbitrary Geometric Configurations // IEEE Trans. Electron. Comput. 1961. Vol. 10, N. 2. P. 260-268.

12. Dopp K. Automaten in Labirinthen. I // Electronische Infor-mationsverarbeitung und Kybernetik. 1971. Vol. 7, N. 2. P. 79-94.

13. Dopp K. Automaten in Labirinthen. II // Electronische Infor-mationsverarbeitung und Kybernetik. 1971. Vol. 7, N. 3. P. 167-190.

14. Budach L. Automata and Labyrinths // Mathematische Nachrichten. 1978. Vol. 86. P. 195-282.

15. Muler H. Automata Catching Labyrinths with at Most Three Components // Elektronische Informationsverarbeitung und Kybernetik. 1979. Vol. 15, N. 1/2. P. 3-9.

16. Зыричев А. Н. О синтезе автомата, обходящего плоские лабиринты с ограниченными дырами // Дискретная математика. 1991. Т. 3, Вып. 1. С. 105-113.

17. Fischer P. C. Multi-Tape and Infinite-State Automata: A survey // Communication of the ACM. 1965. Vol. 8, N. 12. P. 799-805.

18. Antelmann H., Budach L., Rollik H. A. On Universale Traps // Elektronische Infor-mationsverarbeitung und Kybernetik. 1979. Vol. 15, No. 3. P. 123-131.

19. Blum М., Kozen D. On the Power of the Compass // Proc. 19th Annual Symposium on Foundations of Computer Sci. 1978. С. 132-142.

20. Hoffmann F. One pebble does not suffice to search plane labyrinths // Lecture Notes of Computer Science. 1981. Vol. 117. P. 433-444.

21. Ахтеров А. В., Кирильченко А. А., Павловский В. Е., Рогозин К. В. Способы управления распределенной мобильной системой в условиях неопределенности // Препринты ИПМ им. М. В. Келдыша. 2012. № 67. 32 с. URL: http://library.keldysh.ru/ preprint.asp?id = 2012-67.

22. Parsons T. D. Pursuit-Evasion in a Graph / In Theory and Applications of Graphs. Springer-Verlag. 1976. P. 426-441.

23. Megiddo N., Hakimi S. L., Garey M. R., Johnson D. S., Papadimitriou C. H. The Complexity of Searching a Graph // Journal of the ACM. 1988. Vol. 35, N. 1. P. 18-44.

24. Степкин А. В. Использование коллектива агентов для распознавания графа // Компьютерные исследования и моделирование. 2013. Т. 5. № 4. С. 525-532.

25. Сапунов С. В. Восстановление графа с помеченными вершинами перемещающимся по нему мобильным агентом // Известия Саратовского ун-та. Новая серия. Сер. Математика. Механика. Информатика. 2015. Т. 15, Вып. 2. С. 228-238.

26. Теряев Е. Д., Петрин К. В., Филимонов А. Б., Филимонов Н. Б. Агентные технологии в автоматизированных информационно-управляющих системах. Ч. I. Основы агентного подхода // Мехатроника, автоматизация, управление. 2010. № 7. С.11-27.

27. Теряев Е. Д., Петрин К. В., Филимонов А. Б., Филимонов Н. Б. Агентные технологии в автоматизированных информационно-управляющих системах. Ч. II. Агентные решения в задачах контроля и управления // Мехатроника, автоматизация, управление. 2010. № 10. С. 25-34.

28. Макаров И. М., Лохин В. М., Манько С. В., Романов М. П., Крюченков Е. Н., Худак Ю. И., Кучерский Р. В. Модели и алгоритмы планирования действий и распределения заданий в мультиагентных робототехнических системах // Мехатроника, автоматизация, управление. 2012. № 5. С. 44-50.

29. Jennings N. R., Wooldridge M. J. Agent Technology. Berlin; Heidelberg; New-York: Springer-Verlag, 1998.

30. Wooldridge M. J. An Introduction to MultiAgent Systems. John Wiley & Sons Ltd, 2002. 366 p.

31. Рассел С., Норвиг П. Искусственный интеллект: современный подход. М.: ИД "Вильямс", 2007. 1408 с.

32. Городецкий В. И., Грушинский М. С., Хабалов А. В. Мно-гоагентные системы (обзор) // Новости искусственного интеллекта. 1998. № 2. С. 64-116.

33. Швецов А. Н. Агентно-ориентированные системы: от формальных моделей к промышленным приложениям // Все-росс. конкурсный отбор обзорно-аналитических статей по приоритетному направлению "Информационно-телекоммуникационные системы". 2008. 101 с.

34. Ржевский Дж. Мультиагентные системы в логистике и е-коммерции // Interna-tional Conference on Intelligent Manufacturing. Wuhan, China, 1995.

35. Muller J. P. The Design of Intelligent Agents: A Layered Approach. Springer-Verlag, Berlin. 1996.

36. Люгер Дж. Ф. Искусственный интеллект: стратегия и методы решения сложных проблем. М.: Изд. дом "Вильямс", 2005.

37. с.

38. McCarthy J. Situations, Actionsand Causal Laws // Stanford Artificial Intelligence Project: Memo2, 1963.

39. Клыков Ю. И. Ситуационное управление большими системами. М.: Энергия, 1974. 136 с.

40. Поспелов Д. А. Ситуационное управление: теория и практика. М.: Наука, 1986. 288 с.

41. Поспелов Д. А. От коллектива автоматов к мульти-агентным системам // Труды Междунар. семинара "Распределенный искусственный интеллект и многоагентные системы" (DAIMAS'97). СПб., 1997. С. 319-325.

42. Тарасов В. Б. Агенты, многоагентные системы, виртуальные сообщества: стратегическое направление в информатике и искусственном интеллекте // Новости искусственного интеллекта. 1998. № 2. С. 5-64.

43. Siegwart R., Nourbakhsh I. R. Introduction to Autonomous Mobile Robots. Massachusetts: Bradford Book, 2004. 340 p.

44. Choset H., Lynch K. M., Hutchinson S., Kantor G., Burgard W., Kavraki L. E., Thrun S. Principles of Robot Motion: Theory, Algorithms and Implementations. MIT Press, Cambridge, MA, 2005. 603 p.

45. LaValle S. M. Planning Algorithms. Cambridge. U. K.: Cambridge University Press, 2006. 1007 p.

46. Coenen S. A. M., Steinbuch M., van de Molengraft M. J. G., Lunenburg J. J. M., Maus G. J. L. Motion Planning for Mobile Robots: a Guide. Eindhoven, Eindhoven University of Technology. 2012. 79 p.

47. Parker L. E. Path Planning and Motion Coordination in Multiple Mobile Robot Teams. Encyclopedia of Complexity and System Science. R. A. Meyers (ed.). Springer Verlag, 2009. P. 5783- 5800.

48. Desaraju V. R., How J. P. Decentralized Path Planning for Multi-Agent Teams with Complex Constraints // Autonomous Robots. January 2012. P. 1-19.

49. Alonso-Mora J. Collaborative Motion Planning for Multi-Agent Systems, Dr. Diss. Eidgenossische Technische Hochschule ETH Zurich. No 21705. 2014. 176 p.

50. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2013. 1328 с.

51. Rubin F. The Lee path connection algorithm // IEEE Transactions on Computers. 1974. Vol. C-23, Iss. 9. P. 907-914.

52. Волновой алгоритм поиска пути. URL: http:// www.100byte.ru/100btwrks/wv/wv.html.

53. Алдошкин Д. Н., Царев Р. Ю. Поиск пути м обильного робота в условиях наличия препятствий и неполноты информации о среде // Мехатроника, автоматизация, управление. 2016. № 7. С. 465-470.

54. Изотова Т. Ю. Обзор алгоритмов поиска кратчайшего пути в графе // Новые информационные технологии в автоматизированных системах. 2016. Вып. 19. С. 341-344.