Transfer Time Complexity of Conflict-free Vehicle Routing with no Communications

Abstract

The following motion coordination problem is studied: given n mobile vehicles and n source-destination pairs in the plane, what is the minimum time needed to transfer each vehicle from 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. The environment is free of obstacles 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 constant fraction of the n vehicles can be fitted 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 Θ ([UNKNOWN][UNKNOWN]n) time to complete, where [UNKNOWN] 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 Ω(n) time. The case is also analyzed in which source and destination points are generated randomly according to a uniform 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 Θ ([UNKNOWN]n) time, with high probability, thus recovering the best case performance.

Keywords

multi-robot systems motion planning collision avoidance multiple agent system analysis vehicular traffic capacity

Get full access to this article

View all access options for this article.

References

Akella, S. and Hutchinson, S. (2002). Coordinating the motions of multiple robots with specified trajectories. Proceedings of IEEE International Conference on Robotics and Automation, Washington D.C., May, pp. 624–631.

Alami, R. , Robert, F. , Ingrand, F. F. , and Suzuki, S. (1995). Multi-robot cooperation through incremental pathmerging. Proceedings of IEEE International Conference on Robotics and Automation, Nagoya, Japan, pp. 2573–2578.

Bien, Z. and Lee, J. (1992). A minimum-time trajectory planning method for two robots. IEEE Transactions on Robotics and Automation, 8(3): 414–418.

Bryson, A. E. and Ho, Y. C. (1975). Applied Optimal Control. Hemisphere Publishing, New York.

Buckley, S. J. (1989). Fast motion planning for multiple moving robots. Proceedings of IEEE International Conference on Robotics and Automation, Scottsdale, AZ, pp. 322–326.

Chang, C. , Chung, M. J. , and Lee, B. H. (1994). Collision avoidance of two robot manipulators by minimum delay time. IEEE Transactions on Systems, Man, and Cybernetics, 24(3): 517–522.

Chitsaz, H. , O'Kane, J. M. , and La Valle, S. M. (2004). Exact pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap. Proceedings of IEEE International Conference on Robotics and Automation, New Orleans, LA, pp. 3981–3986.

Chlebus, B. S. and Sibeyn, J. F. (2003). Routing on meshes in optimum time and with really small queues. Proceedings of IEEE International Symposium on Parallel and Distributed Processing, Nice, France.

Dunbar, S. R. (1997). The average distance between points in geometric figures. College Mathematics Journal, 28(3): 187–197.

10.

Egerstedt, M. and Brockett, R. (2003). Feedback can reduce the specification complexity of motor programs. IEEE Transactions on Automatic Control, 48(2): 213–223.

11.

Erdmann, M. and Lozano-Pérez, T. (1987). On multiple moving objects. Algorithmica, 2: 477–521.

12.

Ghrist, R. , O'Kane, J. , and La Valle, S. M. (2004). Pareto-optimal coordination on roadmaps. Proceedings of Sixth International Workshop on Algorithmic Foundation of Robotics, Zeist, Netherlands, pp. 171–186.

13.

Grossglauser, M. and Tse, D. (2001). Mobility increases the capacity of wireless ad hoc networks. Proceedings of IEEE INFOCOM, pp. 1360–1369.

14.

Gupta, P. and Kumar, P. R. (2000). The capacity of wireless networks. IEEE Transactions on Information Theory, 46: 388–404.

15.

Hopcroft, J. E. , Schwartz, J. T. , and Sharir, M. (1984). On the complexity of motion planning for multiple independent objects: PSPACE-hardness of the warehouseman's problem. International Journal of Robotics Research, 3: 76–88.

16.

Kant, K. and Zucker, S. W. (1986). Toward efficient trajectory planning: The path-velocity decomposition. International Journal of Robotics Research, 5(3): 72–89.

17.

Klavins, E. (2002). Communication complexity of multi-robot systems. Proceedings of Fifth International Workshop on the Algorithmic Foundations of Robotics, Nice, France.

18.

La Valle, S. M. and Hutchinson, S. A. (1998). Optimal motion planning for multiple robots having independent goals. IEEE Transactions on Robotics and Automation, 14(6): 912–925.

19.

Martinez, S. , Bullo, F. , Cortes, J. , and Frazzoli, E. (2005a). On synchronous robotic networks – Part I: Models, tasks and complexity notions. IEEE Transactions on Automatic Control. Provisionally accepted, pending revision.

20.

Martinez, S. , Bullo, F. , Cortes, J. , and Frazzoli, E. (2005b). On synchronous robotic networks – Part II: Time complexity of rendezvous and deployment algorithms. IEEE Transactions on Automatic Control. Provisionally accepted, pending revision.

21.

Neely, M. D. and Modiano, E. (2003). Improving delay in ad hoc mobile networks via redundant packet transfers. Proceedings of Conference on Information Sciences and Systems, Johns Hopkins University.

22.

O'Donnell, P. A. and Lozano-Pérez, T. (1989). Deadlock-free and collision-free coordination of two robot manipulators. (Proceedings of IEEE International Conference on Robotics and Automation, Scottsdale, AZ, Vol. 1, pp. 484–489.

23.

Papoulis, A. (1984). Probability, Random Variables, and Stochstic Processes, 2nd edn. McGraw-Hill, New York.

24.

Peng, J. and Akella, S. (2002). Coordinating multiple robots with kinodynamic constraints along specified paths. Proceedings of Fifth International Workshop on the Algorithmic Foundations of Robotics (WAFR), Nice, France (eds J.-D. Boissonnat , J. Burdick , K. Goldberg , and S. Hutchinson ), Springer-Verlag, pp. 221–237.

25.

Reif, J. H. (1979). Complexity of the mover's problem and generalizations. Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico, pp. 421–427.

26.

Schwartz, J. T. and Sharir, M. (1983a). On the “piano movers'” problem II. General techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics, 4: 298–351.

27.

Schwartz, J. T. and Sharir, M. (1983b). On the “piano movers'” problem: III. Coordinating the motion of several independent bodies: The special case of circular bodies moving amidst polygonal barriers. International Journal of Robotics Research, 2(3): 46–75.

28.

Schwarz, J. T. and Sharir, M. (1983c). On the “piano movers;” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers. Communications on Pure and Applied Mathematics, 36: 345–398.

29.

Siméon, T. , Leroy, S. , and Laumond, J.-P. (2002). Path coordination for multiple mobile robots: A resolution-complete algorithm. IEEE Transactions on Robotics and Automation, 18(1): 42–49.

30.

Toth, P. and Vigo, T. (eds) (2002). The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA.

31.

West, D. (2000). Introduction to Graph Theory, 2nd edn. Prentice Hall, Englewood Cliffs, NJ.

32.

Xue, F. and Kumar, P. R. (2004). The number of neighbors needed for connectivity of wireless networks. Wireless Networks, 10(2): 169–181.