transparent gif

 

Ej inloggad.

Göteborgs universitets publikationer

When can multi-agent rendezvous be executed in time linear in the diameter of a plane configuration?

Författare och institution:
Peter Hegarty (Institutionen för matematiska vetenskaper, matematik, Chalmers/GU); Anders Martinsson (Institutionen för matematiska vetenskaper, matematik, Chalmers/GU); Dmitrii Zhelezov (Institutionen för matematiska vetenskaper, Chalmers/GU)
Publicerad i:
17th International Conference on Distributed Computing and Networking, ICDCN 2016; Singapore; Singapore; 4 January 2016 through 7 January 2016, s. Art. no. a2
ISBN:
978-1-4503-4032-8
Publikationstyp:
Konferensbidrag, refereegranskat
Publiceringsår:
2016
Språk:
engelska
Fulltextlänk:
Sammanfattning (abstract):
In multi-agent rendezvous it is naturally assumed that agents have a maximum speed of movement. In the absence of any distributed control issues, this imposes a lower bound on the time to rendezvous, for idealised point agents, proportional to the diameter of a configuration. Assuming bounded visibility, we consider Ω(n2 log n) points distributed independently and uniformly at random in a disc of radius n, so that the visibility graph is asymptotically almost surely (a.a.s.) connected. We allow three types of possible interaction between neighbors, which we term signalling, sweeping and tracking. Assuming any such interaction can be executed without significant delay, and assuming each point can generate random bits and has unlimited memory, we describe a randomized algorithm which a.a.s. runs in time O(n), hence in time proportional to the diameter, provided the number of points is o(n3). Several questions are posed for future work.
Ämne (baseras på Högskoleverkets indelning av forskningsämnen):
NATURVETENSKAP ->
Matematik ->
Diskret matematik
NATURVETENSKAP ->
Data- och informationsvetenskap
Chalmers styrkeområden:
Informations- och kommunikationsteknik
Chalmers fundament:
Grundläggande vetenskaper
Postens nummer:
231854
Posten skapad:
2016-02-09 15:32
Posten ändrad:
2016-07-08 15:43

Visa i Endnote-format

Göteborgs universitet • Tel. 031-786 0000
© Göteborgs universitet 2007