Efficient Collision Prediction Among Many Moving Objects

Abstract

We consider the problem of flagging all collisions between a large number of dynamic objects. Because the number of possible collisions grows quadratically with the number of objects, a brute force approach is not applicable with finite computational resources.

Hence, we propose a scheduling mechanism that reduces the computational load by exploiting the coherence of the world throughout time. This mechanism has a very simple structure and easily lends itself to distributed processing. It considers all pairwise interactions between objects and maintains a structure that reflects the imminence, or urgency, of collision for each pair. Bounds on the urgency of collisions can be computed given minimal knowledge of the system dynamics. For example, we represent physical objects by their positions and by bounds on their relative speeds and accelerations. These are assumed to be available at all times. If the environment does not change too rapidly, the mechanism flags all collisions. False alarms may also be generated but can be eliminated with a specialized exact collision post-processor.

We address the question of how often to perform the col lision checks while guaranteeing that all collisions will be caught. Given the large number of possible environments and motions, no general optimal answer can be provided. Yet the soundness and efficiency of the proposed algorithm is eaper imentally verified in the case of a simple world consisting of many spheres moving simultaneously and randomly.

Get full access to this article

View all access options for this article.

References

Aho. A.V. , Hopcroft, J.E. , and Ullman, J.D. 1982. Data Structures and Algorithms. Reading, MA: Addison-Wesley.

Avnaim, F. , Boissonnat, J.-D. , and Faverjon, B. 1988 (May, Philadelphia). A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles . Proc. IEEE International Conference on Robotics and Automation, pp. 1656-1661.

Baraff, D. 1990. Curved surfaces and coherence for non-penetrating rigid body simulation. Computer Graphics 24(4):19-38.

Barford, D.A. 1989 (November, Tempe, AZ). Fast detection of collisions between moving bodies. Proc. SIAM Conference on Geometric Design.

Bobrow, J.E. 1989. A direct minimization approach for obtaining the distance between convex polyhedra. Int. J. Robot. Res. 8(3):65-76.

Boyse, J.W. 1979. Interference detection among solids and surfaces . Comm. ACM 22(1):3-9.

Brooks, R.A. 1983. Solving the find-path problem by good representation of free space. IEEE Trans. Sys. Man Cybernet. 13:190-197.

Brooks, R.A. , and Lozano-Pérez, T. 1983 (Karlsruhe, Germany). A subdivision algorithm in configuration space for findpath with rotation. Proc. International Joint Conference on Artificial Intelligence, pp. 799-806.

Bryson A.E. , and Ho, Y.-C. 1975. Applied Optimal Control. New York: Halsted Press.

10.

Cameron, S. 1985 (March, St. Louis). A study of the clash detection problem in robotics. Proc. IEEE International Conference on Robotics and Automation, pp. 488-493.

11.

Canny, J. 1988. The Complexity of Robot Motion Planning. Cambridge, MA: MIT Press.

12.

Culley, R.K. , and Kempf, K.G. 1986 (April, San Francisco). A collision detection algorithm based on velocity and distance bounds. Proc. IEEE International Conference on Robotics and Automation , pp. 1064-1069.

13.

Dobkin, D.P. , and Kirkpatrick, D.G. 1983. Fast detection of polyhedral intersection. Theoretical Comp. Sci. 27:241-253.

14.

Dobkin, D.P. , and Kirkpatrick, D.G. 1985. A linear algorithm for determining the separation of convex polyhedra. J. Algorithms 6:381-392.

15.

Faverjon, B. , and Tournassoud, P. 1988 (December). A practical approach to motion-planning for a manipulator with many degrees of freedom. Rapport de Recherche 951, INRIA, Sophia Antipolis, France.

16.

Gilbert, E.G. , and Foo, C.P. 1990 (May, Scottsdale, AZ). Computing the distance between smooth objects in three dimensional space. Proc. IEEE International Conference on Robotics and Automation , pp. 158-163.

17.

Gilbert, E.G. , and Hong, S.M. 1990 (May, Scottsdale, AZ). A new algorithm for detecting the collision of moving objects. Proc. IEEE International Conference on Robotics and Automation , pp. 8-14.

18.

Gilbert, E.G. , and Johnson, D.W. 1985. Distance functions and their application to robot path planning in the presence of obstacles. IEEE Trans. Robot. Automation 1(1):21-30.

19.

Gilbert, E.G. , Johnson, D.W. , and Keerthi, S.S. 1988. A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Trans. Robot. Automation 4(2):193-203.

20.

Hayward, V. , and Aubry, S. 1987 (October, Cambridge, MA). On describing a robotic scene. Proc. SPIE Conference on Intelligent Robots and Computer Vision: Sixth in a Series Bellingham, WA: SPIE, pp. 525-532.

21.

Hurteau, G. , and Stewart, N.F. 1988. Distance calculation for imminent collision indication in a robot system simulation. Robotica 6:47-51.

22.

Kawabe, S. , Okano, A.K. , and Shima, K. 1988. Collision detection among moving objects in simulation . In Bolles, R. C. , and Roth, B. (eds.): Fourth International Symposium on Robotics Research. Cambridge, MA: MIT Press, pp. 489-496.

23.

Lawden, D.F. 1963. Optimal Trajectories for Space Navigation. London: Butterworths.

24.

Lin, M.C. , and Canny, F.F. 1991 (April, Sacremento, CA). A fast algorithm of incremental distance calculation. Proc. IEEE International Conference on Robotics and Automation, pp. 1008-1014.

25.

Lozano-Pérez, T. 1983. Spatial planning: A configuration space approach . IEEE Trans. Computers 32:108-120.

26.

Lozano-Pérez, T. 1987. A simple motion-planning algorithm for general robot manipulators . IEEE Trans. Robot. Automation 3(3):224-238.

27.

Lozano-Pérez, T. , and Wesley, M.A. 1979. An algorithm for planning collision-free paths among polyhedral obstacles. Comm. ACM 22:560-570.

28.

Luenberger, D.G. 1969. Optimization by Vector Space Methods. New York: Wiley.

29.

O'Rourke, J. , and Badler, N. 1979

(July). Decomposition of three-dimensional objects into spheres. IEEE Transactions of Pattern Analysis and

Machine Intelligence, 1(1):295-305.

30.

Powell, M.J.D. 1985. On the quadratic programming algorithm of Goldfarb and Idnani. Math. Program. Study 25:46-61.

31.

Red, W.E. 1983. Minimum distances for robot task simulation. Robotica 1:231-238.

32.

Roider, B. , and Stifter, B. 1987. Collision of convex objects. In Davenport, J. H. (ed.): Eurocal. (LNCS). New York: Springer-Verlag, pp. 258-259.

33.

Stifter, S. 1988. A generalization of the Roider method to solve the robot collision problem. In Gianni, P. (ed.): Proc. International Symposium on Symbolic and Algebraic Computation. New York: Springer-Verlag , pp. 332-343.