Transfer Time Complexity Of Conflict-Free Vehicle Routing With No Communications  

Oleh:

[s.n]

Jenis: Article from Journal - ilmiah internasional
Dalam koleksi: The International Journal of Robotics Research vol. 26 no. 3 (Mar. 2007), page 255-272.
Topik: multi-robot systems; motion planning; collision avoidance; multiple agent system analysis; vehicular traffic capacity
Fulltext: 255.pdf (3.71MB)

Isi artikel

vehicles and n source-destination pairs in the plane, what is the minimum time needed to transfer each vehiclefrom its source to its destination, avoiding conflicts with other vehicles? In the proposed model, vehicles do not explicitly communicate their intentions, and only have sensory information about the current position and velocity of their neighbors to ensure no conflicts. 7he environment isfree ofobstacles and a conflict occurs when the distance between any two vehicles is smaller than a velocity-dependent safety distance. The situation analyzed in which the vehicle size is such that at least a constantfraction ofthe n vehicles can befitted inside the environment simultaneously. In the "best" case in which the source and destination points can be chosen ideally to maximize the transfer efficiency, it is shown that the transfer takes e(LvAi) time to complete, where L is the average distance between the source and destination points. It is shown that there exist a "worst" case distribution of the source and destination points, for which the transfer of vehicles takes at least Q (n) time. 77Te case is also analyzed in which source and destination points are generated randomly according to a unifonn distribution, and an algorithm is presented providing a constructive upper bound on the time needed to transfer vehicles from sources to their corresponding destinations, proving that the transfer takes e(GIu) time, with high probability, thus recovering the best case performance.

Opini Anda

Klik untuk menuliskan opini Anda tentang koleksi ini!

Kembali