Till sidans topp

Sidansvarig: Webbredaktion
Sidan uppdaterades: 2012-09-11 15:12

Tipsa en vän
Utskriftsversion

A variant of the multi-ag… - Göteborgs universitet Till startsida
Webbkarta
Till innehåll Läs mer om hur kakor används på gu.se

A variant of the multi-agent rendezvous problem

Övrigt
Författare Peter Hegarty
Anders Martinsson
Dmitrii Zhelezov
Publiceringsår 2013
Publicerad vid Institutionen för matematiska vetenskaper
Institutionen för matematiska vetenskaper, matematik
Språk en
Länkar www.math.chalmers.se/~hegarty/termi...
Ämnesord Multi-agent rendezvous, random geometric graph, randomized algorithm
Ämneskategorier Diskret matematik, Sannolikhetsteori och statistik, Datorseende och robotik (autonoma system), Annan data- och informationsvetenskap

Sammanfattning

The classical multi-agent rendezvous problem asks for a deterministic algorithm by which $n$ points scattered in a plane can move about at constant speed and merge at a single point, assuming each point can use only the locations of the others it sees when making decisions and that the visibility graph as a whole is connected. In time complexity analyses of such algorithms, only the number of rounds of computation required are usually considered, not the amount of computation done per round. In this paper, we consider $\Omega(n^2 \log n)$ points distributed independently and uniformly at random in a disc of radius $n$ and, assuming each point can not only see but also, in principle, communicate with others within unit distance, seek a randomised merging algorithm which asymptotically almost surely (a.a.s.) runs in time $O(n)$, in other words in time linear in the radius of the disc rather than in the number of points. Under a precise set of assumptions concerning the communication capabilities of neighboring points, we describe an algorithm which a.a.s. runs in time $O(n)$ provided the number of points is $o(n^3)$. Several questions are posed for future work.

Sidansvarig: Webbredaktion|Sidan uppdaterades: 2012-09-11
Dela:

På Göteborgs universitet använder vi kakor (cookies) för att webbplatsen ska fungera på ett bra sätt för dig. Genom att surfa vidare godkänner du att vi använder kakor.  Vad är kakor?