Мультиагентная задача о роботах в пространстве: сложностно́й, информационный и криптографический аспекты
А. Ю. Бернштейнa,
Н. В. Шиловb a Новосибирский государственный университет,
630090, г. Новосибирск, ул. Пирогова, д. 2
b Институт систем информатики им. А. П. Ершова,
630090, г. Новосибирск, проспект Лаврентьева, 6
Аннотация:
В статье изучается следующая мультиагентная алгоритмическая
задача о роботах в пространстве (Robot in Space — RinS):
В пространстве есть $n\geq 2$ автономных робота, которым необходимо самостоятельно договориться о выборе индивидуальных укрытий так, чтобы прямолинейные маршруты к этим укрытиям не пересекались. Эта задача имеет отношение к
задаче о назначениях в теории графов,
задаче построения выпуклой оболочки в комбинаторной геометрии и
задаче планирования перемещений в искусственном интеллекте. Предлагаемый в статье мультиагентный алгоритм (протокол) основан на централизованном локальном алгоритме Э. В. Дейкстры. Наш алгоритм обладает свойствами анонимности и масштабируемости, мы доказываем его корректность и верхнюю оценку сложности. Кроме того, мы исследуем два коммуникационных аспекта задачи о роботах в пространстве —
информационный и
криптографический. В статье показано, что (1) не существует протокола, решающего задачу RinS, передающего ограниченное число битов, но (2) существует протокол для решения этой задачи, который позволяет роботам не раскрывать информацию о своём положении относительно укрытий. Настоящая статья является продолжением исследований, представленных в статье Е. В. Бодина, Н. О. Гараниной и Н. В. Шилова
"Задача о роботах на Марсе (мультиагентный подход к задаче Дейкстры)" опубликованной в № 2 за 2011 г. журнала
"Моделирование и анализ информационных систем".
Ключевые слова:
мультиагентные (многоагентные) системы и алгоритмы, геометрическая задача о назначениях, анонимность, масштабируемость, свойства безопасности и прогресса, верификация алгоритмов.
УДК:
519.7+
519.8+004.8
Поступила в редакцию: 18.06.2012