RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Model. Anal. Inform. Sist., 2013, Volume 20, Number 2, Pages 34–53 (Mi mais296)  

“Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic Aspects

A. Yu. Bernsteina, N. V. Shilovb

a Novosibirsk State University, Pirogova Str., 2, Novosibirsk, 630090, Russia
b A. P. Ershov Institute of Informatics Systems SB RAS, prospect Akademika Lavrentjeva, 6, Novosibirsk, 630090, Russia

Abstract: We study a multiagent algorithmic problem that we call Robot in Space (RinS): There are $n\geq 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.

Keywords: multiagent systems and algorithms, location assignment problem, anonymity, scalability, safety and progress properties, algorithm verification.

Full text: PDF file (699 kB)
References: PDF file   HTML file

Document Type: Article
UDC: 519.7+519.8+004.8
Received: 18.06.2012

Citation: A. Yu. Bernstein, N. V. Shilov, ““Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic Aspects”, Model. Anal. Inform. Sist., 20:2 (2013), 34–53

Citation in format AMSBIB
\Bibitem{BerShi13}
\by A.~Yu.~Bernstein, N.~V.~Shilov
\paper ``Robots in Space'' Multiagent Problem: Complexity, Information and Cryptographic Aspects
\jour Model. Anal. Inform. Sist.
\yr 2013
\vol 20
\issue 2
\pages 34--53
\mathnet{http://mi.mathnet.ru/mais296}


Linking options:
  • http://mi.mathnet.ru/eng/mais296
  • http://mi.mathnet.ru/eng/mais/v20/i2/p34

    SHARE: 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
    Cycle of papers
  • Моделирование и анализ информационных систем
    Number of views:
    This page:212
    Full text:60
    References:17

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019