“Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic Aspects
We study a multiagent algorithmic problem that we call Robot in Space (RinS): There are n ≥ 2 autonomous robots, that need to agree without outside interference on distribution of shelters, so that straight pathes to the shelters will not intersect. The problem is closely related to the assignment p...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2013-04-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/204 |
| _version_ | 1797877980997877760 |
|---|---|
| author | A. Yu. Bernstein N. V. Shilov |
| author_facet | A. Yu. Bernstein N. V. Shilov |
| author_sort | A. Yu. Bernstein |
| collection | DOAJ |
| description | We study a multiagent algorithmic problem that we call Robot in Space (RinS): There are n ≥ 2 autonomous robots, that need to agree without outside interference on distribution of shelters, so that straight pathes to the shelters will not intersect. The problem is closely related to the assignment problem in Graph Theory, to the convex hull problem in Combinatorial Geometry, or to the path-planning problem in Artificial Intelligence. Our algorithm grew up from a local search solution of the problem suggested by E.W. Dijkstra. We present a multiagent anonymous and scalable algorithm (protocol) solving the problem, give an upper bound for the algorithm, prove (manually) its correctness, and examine two communication aspects of the RinS problem — the informational and cryptographic. We proved that (1) there is no protocol that solves the RinS, which transfers a bounded number of bits, and (2) suggested the protocol that allows robots to check whether their paths intersect, without revealing additional information about their relative positions (with respect to shelters). The present paper continues the research presented in Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem) (by E.V. Bodin, N.O. Garanina, and N.V. Shilov), published in Modeling and analysis of information systems, 18(2), 2011. |
| first_indexed | 2024-04-10T02:25:29Z |
| format | Article |
| id | doaj.art-e64f431b9e9344539447514476f66a58 |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-10T02:25:29Z |
| publishDate | 2013-04-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-e64f431b9e9344539447514476f66a582023-03-13T08:07:31ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172013-04-01202345310.18255/1818-1015-2013-2-34-53198“Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic AspectsA. Yu. Bernstein0N. V. Shilov1Новосибирский государственный университетИнститут систем информатики им. А.П. Ершова СО РАНWe study a multiagent algorithmic problem that we call Robot in Space (RinS): There are n ≥ 2 autonomous robots, that need to agree without outside interference on distribution of shelters, so that straight pathes to the shelters will not intersect. The problem is closely related to the assignment problem in Graph Theory, to the convex hull problem in Combinatorial Geometry, or to the path-planning problem in Artificial Intelligence. Our algorithm grew up from a local search solution of the problem suggested by E.W. Dijkstra. We present a multiagent anonymous and scalable algorithm (protocol) solving the problem, give an upper bound for the algorithm, prove (manually) its correctness, and examine two communication aspects of the RinS problem — the informational and cryptographic. We proved that (1) there is no protocol that solves the RinS, which transfers a bounded number of bits, and (2) suggested the protocol that allows robots to check whether their paths intersect, without revealing additional information about their relative positions (with respect to shelters). The present paper continues the research presented in Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem) (by E.V. Bodin, N.O. Garanina, and N.V. Shilov), published in Modeling and analysis of information systems, 18(2), 2011.https://www.mais-journal.ru/jour/article/view/204мультиагентные (многоагентные) системы и алгоритмыгеометрическая задача о назначенияханонимностьмасштабируемостьсвойства безопасности и прогрессаверификация алгоритмов |
| spellingShingle | A. Yu. Bernstein N. V. Shilov “Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic Aspects Моделирование и анализ информационных систем мультиагентные (многоагентные) системы и алгоритмы геометрическая задача о назначениях анонимность масштабируемость свойства безопасности и прогресса верификация алгоритмов |
| title | “Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic Aspects |
| title_full | “Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic Aspects |
| title_fullStr | “Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic Aspects |
| title_full_unstemmed | “Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic Aspects |
| title_short | “Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic Aspects |
| title_sort | robots in space multiagent problem complexity information and cryptographic aspects |
| topic | мультиагентные (многоагентные) системы и алгоритмы геометрическая задача о назначениях анонимность масштабируемость свойства безопасности и прогресса верификация алгоритмов |
| url | https://www.mais-journal.ru/jour/article/view/204 |
| work_keys_str_mv | AT ayubernstein robotsinspacemultiagentproblemcomplexityinformationandcryptographicaspects AT nvshilov robotsinspacemultiagentproblemcomplexityinformationandcryptographicaspects |