Мультиагентная задача о роботах в пространстве: сложностно́й, информационный и криптографический аспекты

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