{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:50:03Z","timestamp":1777715403431,"version":"3.51.4"},"reference-count":33,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[1995,4,1]],"date-time":"1995-04-01T00:00:00Z","timestamp":796694400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[1995,4]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1177\/027836499501400203","type":"journal-article","created":{"date-parts":[[2007,3,4]],"date-time":"2007-03-04T20:24:06Z","timestamp":1173039846000},"page":"129-143","source":"Crossref","is-referenced-by-count":21,"title":["Efficient Collision Prediction Among Many Moving Objects"],"prefix":"10.1177","volume":"14","author":[{"given":"Vincent","family":"Hayward","sequence":"first","affiliation":[{"name":"Electrical Engineering Department and Center for Intelligent Machines McGill University Montr\u00e9al, Qu\u00e9bec, Canada H3A 2A7"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Aubry","sequence":"additional","affiliation":[{"name":"Electrical Engineering Department and Center for Intelligent Machines McGill University Montr\u00e9al, Qu\u00e9bec, Canada H3A 2A7"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Foisy","sequence":"additional","affiliation":[{"name":"Electrical Engineering Department and Center for Intelligent Machines McGill University Montr\u00e9al, Qu\u00e9bec, Canada H3A 2A7"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasmine","family":"Ghallab","sequence":"additional","affiliation":[{"name":"Electrical Engineering Department and Center for Intelligent Machines McGill University Montr\u00e9al, Qu\u00e9bec, Canada H3A 2A7"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[1995,4,1]]},"reference":[{"key":"atypb1","volume-title":"Data Structures and Algorithms","author":"Aho. A.V.","year":"1982"},{"key":"atypb2","volume-title":"Proc. IEEE International Conference on Robotics and Automation","author":"Avnaim, F."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/97880.97881"},{"key":"atypb4","volume-title":"Proc. SIAM Conference on Geometric Design","author":"Barford, D.A."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1177\/027836498900800304"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/359046.359048"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1983.6313112"},{"key":"atypb8","volume-title":"Proc. International Joint Conference on Artificial Intelligence","author":"Brooks, R.A."},{"key":"atypb9","volume-title":"Applied Optimal Control","author":"Bryson A.E.","year":"1975"},{"key":"atypb10","volume-title":"Proc. IEEE International Conference on Robotics and Automation","author":"Cameron, S."},{"key":"atypb11","volume-title":"The Complexity of Robot Motion Planning","author":"Canny, J.","year":"1988"},{"key":"atypb12","volume-title":"Proc. IEEE International Conference on Robotics and Automation","author":"Culley, R.K."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90120-7"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90007-0"},{"key":"atypb15","unstructured":"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."},{"key":"atypb16","volume-title":"Proc. IEEE International Conference on Robotics and Automation","author":"Gilbert, E.G."},{"key":"atypb17","volume-title":"Proc. IEEE International Conference on Robotics and Automation","author":"Gilbert, E.G."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/JRA.1985.1087003"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/56.2083"},{"key":"atypb20","volume-title":"Proc. SPIE Conference on Intelligent Robots and Computer Vision: Sixth in a Series","author":"Hayward, V."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1017\/S0263574700003593"},{"key":"atypb22","unstructured":"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."},{"key":"atypb23","volume-title":"Optimal Trajectories for Space Navigation","author":"Lawden, D.F.","year":"1963"},{"key":"atypb24","volume-title":"Proc. IEEE International Conference on Robotics and Automation","author":"Lin, M.C."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676196"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1109\/JRA.1987.1087095"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"atypb28","volume-title":"Optimization by Vector Space Methods","author":"Luenberger, D.G.","year":"1969"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1979.4766925"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121074"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1017\/S0263574700002162"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"Roider, B., and Stifter, B. 1987. Collision of convex objects. In Davenport, J. H. (ed.): Eurocal. (LNCS). New York: Springer-Verlag, pp. 258-259.","DOI":"10.1007\/3-540-51517-8_124"},{"key":"atypb33","volume-title":"Proc. International Symposium on Symbolic and Algebraic Computation","author":"Stifter, S."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499501400203","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499501400203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:03Z","timestamp":1777457703000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/027836499501400203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,4]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,4]]}},"alternative-id":["10.1177\/027836499501400203"],"URL":"https:\/\/doi.org\/10.1177\/027836499501400203","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,4]]}}}