The Problem of Maze Passage by the Intelligent Agents

The problems of the analysis and passage of the unknown medium by wandering automata over it is the subject of the study of the theoretical computer science. The maze is very popular geometric model of such medium. The mazes as the artificial testing medium for the experimental research of traffic control algorithms of the autonomous mobile robots are widely used in robotics. The paper is dedicated to the problems of maze passage by robotic intelligent agents (IA). The most principle aspects of the algorithmization of mobile robots conduct may be study by means of computer simulation of maze search. The conception of virtual mazes and virtual robots living in them is discussed in the article. It is given the short review of the results of the theoretical researches of the final automata conduct in chess mazes. They permit to understand the possibilities of mazes passage by the reactive agents. The problem of going around of mazes by the IA occupies the central place in the article. The IA in contrast to the reactive agents are capable to analyze the habitat, to design and optimize its own conduct. In connection with it the statement of the maze problems is changed cardinally. The architecture of the IA which are able to decide the wide class of the maze problems is analyzed. The question of the structure of the situating models of IA conduct occupies the central place in the article. The simplest situating model of the agents' conduct is the static one and it is constructed on the basis of the productions "situation-action". But for the planning ofIA conduct it is necessary the dynamic situating model complemented with the event mechanism of the situations control. In this case the cycle of control by the agent conduct has the following stages: the analysis of the situation - the generation of local purpose - the planning of actions - the fulfillment of plan. The formal scheme of the structure of the mathematical models of the situating control processes and the planning of the actions of the IA is proposed. The considerations about the co-ordination of the agents' actions are reduced. The method of the optimization of the routes of the movement in the maze based on the reduction of the initial optimization problems for the checked maze to more simple problem of search of the shortest route of the weigh graphs is suggested.

шахматный лабиринт, поведение автоматов, интеллектуальные агенты, архитектура, ситуационная модель поведения, планирование действий, оптимизация маршрутов, 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.