Задача о роботах на Марсе (мультиагентный подход к задаче Дейкстры)

Евгений Викторович Бодин; Наталья Олеговна Гаранина; Николай Вячеславович Шилов

doi:10.18255/1818-1015-2011-2-113-128

Задача о роботах на Марсе (мультиагентный подход к задаче Дейкстры)

Евгений Викторович Бодин, Наталья Олеговна Гаранина, Николай Вячеславович Шилов

https://doi.org/10.18255/1818-1015-2011-2-113-128

Полный текст:

Аннотация

Изучаются мультиагентные алгоритмы для так называемой задачи о роботах на Марсе. Эту задачу можно рассматривать как задачу из теории графов (дискретная математика), как комбинаторную геометрическую задачу (теоретическое программирование) или как частный случай задачи планирования перемещений (искусственный интеллект). Наши алгоритмы основаны на эвристическом поиске, предложенном Э. Дейкстрой. В статье представлен ряд новых мультиагентных алгоритмов, решающих задачи о роботах на Марсе, доказана их корректность, приведены результаты проверки на модели некоторых из этих алгоритмов, предложены направления дальнейших исследований. Новизна представленной работы состоит в том, что в отличие от теоретико-графового и комбинаторно-геометрического подходов, ориентированных на централизованное решение задачи, мы развиваем мультиагентный подход, но, в свою очередь, наша работа отличается от работ по планированию перемещений математической строгостью доказательств корректности предложенных алгоритмов. Я, робот.
А. Азимов

Ключ. слова

мультиагентная система, распределённый алгоритм, задача о назначениях, планирование перемещений,

УДК: 004.896 + 519.713

Об авторах

Евгений Викторович Бодин

Институт Систем Информатики им. А.П. Ершова СО РАН
Россия

Наталья Олеговна Гаранина

Институт Систем Информатики им. А.П. Ершова СО РАН
Россия

Николай Вячеславович Шилов

Институт Систем Информатики им. А.П. Ершова СО РАН
Россия

Список литературы

1. Fagin R., Halpern J.Y., Moses Y., Vardi M.Y. Reasoning about Knowledge. London: MIT Press, 1995.

2. Garanina N.O., Shilov N.V., and Konyaev L.E. Can Robots Solve the Assignment Problem? // Proc. Int. Workshop on Concurrency, Specification, and Programming.Krakow-Przegorzaly, Poland, 2009. V. 1. P. 154-163.

3. LaValle S.M. Planning Algorithms. Cambridge University Press, 2006.

4. Shilov N.V., Garanina N.O. Modal Logics for reasoning about Multiagent Systems // Encyclopedia of Artificial Intelligence. J.R. Rabucal, J. Dorado, A.P. Sierra, editors. Information Science Reference, 2008. P. 1089-1094.

5. Shilov N.V., Shilova S.O. Etude on theme of Dijkstra // ACM SIGACT News. 2004. V. 35(3). P. 102-108.

6. Shilov N.V., Shilova S.O. On Mathematical Contents of Computer Science Contests // Proc. the 1st KAIST International Symposium on Enhancing University Mathematics Teaching. Daejeon, Korea, 2005. P. 223-233.

7. Wooldridge M. An Introduction to Multiagent Systems. John Willey & Sons Ltd, 2002.

8. Болтянский В.Г., Солтан П.С. Комбинаторная геометрия различных классов выпуклых множеств. Кишинев: Штиинца, 1978.

9. Бугайченко Д.Ю., Соловьев И.П. Абстрактная архитектура интеллектуального агента и методы её реализации // Системное программирование. СПб,2005.С. 36-66.

10. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

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

12. Тель Ж. Введение в распределенные алгоритмы. М.: МЦНМО, 2009.

13. Хадвигер Г., Дебруннер Г. Комбинаторная геометрия плоскости. М.: Наука, 1965.

14. Черемисинов Д., Черемисинова Л. Подход к программированию агентов в мультиагентных системах // International Book Series "Information Science and Computing". 2008. № 4. С. 141-147.

Дополнительные файлы

Для цитирования: Бодин Е.В., Гаранина Н.О., Шилов Н.В. Задача о роботах на Марсе (мультиагентный подход к задаче Дейкстры). Моделирование и анализ информационных систем. 2011;18(2):113-128. https://doi.org/10.18255/1818-1015-2011-2-113-128

For citation: Bodin E.V., Garanina N.O., Shilov N.V. Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem). Modeling and Analysis of Information Systems. 2011;18(2):113-128. (In Russ.) https://doi.org/10.18255/1818-1015-2011-2-113-128

Обратные ссылки

Обратные ссылки не определены.

Контент доступен под лицензией Creative Commons Attribution 4.0 License.

ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)

Логин
Пароль