RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Модел. и анализ информ. систем, 2013, том 20, номер 2, страницы 34–53 (Mi mais296)  

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

А. Ю. Бернштейнa, Н. В. Шиловb

a Новосибирский государственный университет, 630090, г. Новосибирск, ул. Пирогова, д. 2
b Институт систем информатики им. А. П. Ершова, 630090, г. Новосибирск, проспект Лаврентьева, 6

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

Ключевые слова: мультиагентные (многоагентные) системы и алгоритмы, геометрическая задача о назначениях, анонимность, масштабируемость, свойства безопасности и прогресса, верификация алгоритмов.

Полный текст: PDF файл (699 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.7+519.8+004.8
Поступила в редакцию: 18.06.2012

Образец цитирования: А. Ю. Бернштейн, Н. В. Шилов, “Мультиагентная задача о роботах в пространстве: сложностно́й, информационный и криптографический аспекты”, Модел. и анализ информ. систем, 20:2 (2013), 34–53

Цитирование в формате AMSBIB
\RBibitem{BerShi13}
\by А.~Ю.~Бернштейн, Н.~В.~Шилов
\paper Мультиагентная задача о роботах в пространстве: сложностн\'ой, информационный и криптографический аспекты
\jour Модел. и анализ информ. систем
\yr 2013
\vol 20
\issue 2
\pages 34--53
\mathnet{http://mi.mathnet.ru/mais296}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais296
  • http://mi.mathnet.ru/rus/mais/v20/i2/p34

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Цикл статей
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:208
    Полный текст:60
    Литература:17

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019