ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
An algorithm for planning collision-free paths among polyhedral obstacles
Full text PdfPdf (829 KB)
Source
Communications of the ACM archive
Volume 22 ,  Issue 10  (October 1979) table of contents
Pages: 560 - 570  
Year of Publication: 1979
ISSN:0001-0782
Authors
Tomás Lozano-Pérez  Massachusetts Institute of Technology, Cambridge
Michael A. Wesley  IBM Thomas J. Watson Research Center, Yorktown Heights, NY
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 33,   Downloads (12 Months): 131,   Citation Count: 89
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/359156.359164
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
Adamowicz, M., and Albano, A. Nesting two-dimensional shapes in rectangular modules. Comptr. Aided Design 8, 1 (Jan. 1976), 27-33.
2
John W. Boyse, Interference detection among solids and surfaces, Communications of the ACM, v.22 n.1, p.3-9, Jan. 1979  [doi>10.1145/359046.359048]
 
3
Braid, I.C. Designing with Volumes. Cantab Press, Cambridge, England, 1973.
 
4
Hart, P., Nilsson, N.J., and Raphael, B. A formal basis for the heuristic determination of minimum cost paths. 1EEE Trans. Syst. Sci. CybernetiesSSC-4, 2 (July 1968), 100-107.
 
5
Ignat'yev, M.B., Kulakov, F.M., and Pokrovskiy, A.M. Robot manipulator control algorithms. Rep. No. JPRS 59717, NTIS, Springfield, Va., Aug. 1973.
 
6
Tomas Lozano-Perez, The Design of a Mechanical Assembly System, Massachusetts Institute of Technology, Cambridge, MA, 1976
 
7
Lyusternik, L.A. Convex Figures and Polyhedra. Dover Publications, N.Y., 1963. (Translated from the Russian by T.J. Smith; original copyright Moscow, 1956. )
 
8
Nilsson, N.J. A mobile automaton: An application of artificial intelligence techniques. Proc. Int. Joint Conf. Artif. Intell., 1969, pp. 509-520.
9
Shriram Mahabal Udupa, Collision detection and avoidance in computer controlled manipulators., 1977
 
10
Will, P.M., and Grossman, D.D. An experimental system for computer controlled mechanical assembly. IEEE Trans. Comptrs. (1975), 879-888.

CITED BY  89
L. J. Guibas , M. Sharir , S. Sifrony, On the general motion planning problem with two degrees of freedom, Proceedings of the fourth annual symposium on Computational geometry, p.289-298, June 06-08, 1988, Urbana-Champaign, Illinois, United States
Guilherme N. DeSouza , Avinash C. Kak, Vision for Mobile Robot Navigation: A Survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.2, p.237-267, February 2002
Yong Tsui Lee , Aristides A. G. Requicha, Algorithms for computing the volume and other integral properties of solids. II. A family of algorithms based on representation conversion and cellular approximation, Communications of the ACM, v.25 n.9, p.642-650, Sept 1982
A. Meystel , A. Guez , G. Hillel, Minimum time path planning for robot motion in obstacle strewn environment, Proceedings of the 1986 ACM fourteenth annual conference on Computer science, p.367-376, February 1986, Cincinnati, Ohio, United States
Shi-Nine Yang , Ming-Liang Huang, A new offsetting algorithm based on tracing technique, Proceedings on the second ACM symposium on Solid modeling and applications, p.201-210, May 19-21, 1993, Montreal, Quebec, Canada
M. Atallah , D. Chen, Parallel rectilinear shortest paths with rectangular obstacles, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.270-279, July 02-06, 1990, Island of Crete, Greece
Colm ó'Dúnlaing , Micha Sharir , Chee K. Yap, Retraction: A new approach to motion-planning, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.207-220, December 1983
Alex Meystel, Intelligent module for planning/control of master-dependent systems, Proceedings of the 1st international conference on Industrial and engineering applications of artificial intelligence and expert systems, p.620-628, June 1988, Tullahoma, Tennessee, United States
Alex C.-C. Meng , Vytas B. Gylys, A methodology of autonomous navigation in 3-D space under location uncertainty, Proceedings of the 1st international conference on Industrial and engineering applications of artificial intelligence and expert systems, p.605-619, June 1988, Tullahoma, Tennessee, United States
John E. Hopcroft, The impact of robotics on computer science, Communications of the ACM, v.29 n.6, p.486-498, June 1986
John Hershberger , Subhash Suri, Practical methods for approximating shortest paths on a convex polytope in R3, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.447-456, January 22-24, 1995, San Francisco, California, United States
Y. Goto , K. Matsuzaki , I. Kweon , T. Obatake, CMU sidewalk navigation system: a blackboard-based outdoor navigation system using sensor fusion with colored-range images, Proceedings of 1986 ACM Fall joint computer conference, p.105-113, November 1986, Dallas, Texas, United States
Yong K. Hwang , Narendra Ahuja, Gross motion planning—a survey, ACM Computing Surveys (CSUR), v.24 n.3, p.219-291, Sept. 1992
David Kirkpatrick , Jack Snoeyink , Bettina Speckmann, Kinetic collision detection for simple polygons, Proceedings of the sixteenth annual symposium on Computational geometry, p.322-330, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
Young-il Lee , Yong-Gi Kim , Ladislav J. Kohout, An intelligent collision avoidance system for AUVs using fuzzy relational products, Information Sciences—Informatics and Computer Science: An International Journal, v.158 n.1, p.209-232, January 2004
Danny Z. Chen, Developing algorithms and software for geometric path planning problems, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996
Helmut Alt , Rudolf Fleischer , Michael Kaufmann , Kurt Mehlhorn , Stefan Näher , Stefan Schirra , Christian Uhrig, Approximate motion planning and the complexity of the boundary of the union of simple geometric figures, Proceedings of the sixth annual symposium on Computational geometry, p.281-289, June 07-09, 1990, Berkley, California, United States
Brouno Delaunoit , Rodolphe Alimenti , Marc Bogaert, Heuristic control system for autonomous navigation, Proceedings of the 1st international conference on Industrial and engineering applications of artificial intelligence and expert systems, p.570-581, June 1988, Tullahoma, Tennessee, United States
M. H. Overmars , E. Welzl, New methods for computing visibility graphs, Proceedings of the fourth annual symposium on Computational geometry, p.164-171, June 06-08, 1988, Urbana-Champaign, Illinois, United States
J. Canny , B. Donald, Simplified Voronoi diagrams, Proceedings of the third annual symposium on Computational geometry, p.153-161, June 08-10, 1987, Waterloo, Ontario, Canada
K. Clarkson , S. Kapoor , P. Vaidya, Rectilinear shortest paths through polygonal obstacles in O(n(logn)2) time, Proceedings of the third annual symposium on Computational geometry, p.251-257, June 08-10, 1987, Waterloo, Ontario, Canada
Fabio M. Marchese, A directional diffusion algorithm on cellular automata for robot path-planning, Future Generation Computer Systems, v.18 n.7, p.983-994, August, 2002
C. Bajaj , M. Kim, Compliant motion planning with geometric models, Proceedings of the third annual symposium on Computational geometry, p.171-180, June 08-10, 1987, Waterloo, Ontario, Canada
Jim Wang , Verlynda S. Dobbs , Henry W. Davis, Using focusing search algorithms and a strong heuristic to solve the findpath problem in robotics, Proceedings of the 1990 ACM annual conference on Cooperation, p.63-69, February 20-22, 1990, Washington, D.C., United States
John Reif , Micha Sharir, Motion planning in the presence of moving obstacles, Journal of the ACM (JACM), v.41 n.4, p.764-790, July 1994
D. T. Lee , T. H. Chen , C. D. Yang, Shortest rectilinear paths among weighted obstacles, Proceedings of the sixth annual symposium on Computational geometry, p.301-310, June 07-09, 1990, Berkley, California, United States
D. T. Lee , C. D. Yang , C. K. Wong, On Bends and Distances of Paths Among Obstacles in Two-Layer Interconnection Model, IEEE Transactions on Computers, v.43 n.6, p.711-724, June 1994
William J. Schroeder , William E. Lorensen , Steve Linthicum, Implicit modeling of swept surfaces and volumes, Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.
Michael A. Erdmann, Protein similarity from knot theory and geometric convolution, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.195-204, March 27-31, 2004, San Diego, California, USA
G. Wilfong, Motion planning in the presence of movable obstacles, Proceedings of the fourth annual symposium on Computational geometry, p.279-288, June 06-08, 1988, Urbana-Champaign, Illinois, United States
J. Friedman , J. Hershberger , J. Snoeyink, Compliant motion in a simple polygon, Proceedings of the fifth annual symposium on Computational geometry, p.175-186, June 05-07, 1989, Saarbruchen, West Germany
James A. Storer , John H. Reif, Shortest paths in the plane with polygonal obstacles, Journal of the ACM (JACM), v.41 n.5, p.982-1012, Sept. 1994
R. Wolfe , W. Fitzgerald , F. Gracer, Interactive graphics for volume modeling, Proceedings of the 18th conference on Design automation, p.463-470, June 29-July 01, 1981, Nashville, Tennessee, United States
Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.289-298, Aug. 1988
Jed Lengyel , Mark Reichert , Bruce R. Donald , Donald P. Greenberg, Real-time robot motion planning using rasterizing computer graphics hardware, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.327-335, Aug. 1990
Maxim Garber , Ming C. Lin, Constraint-based motion planning for virtual prototyping, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
Jing-Fu Fu Jeng , Wing Ning Li, Optimal hypercube algorithms for robot configuration space computation, Proceedings of the 1995 ACM symposium on Applied computing, p.182-186, February 26-28, 1995, Nashville, Tennessee, United States
D. Halperin , M. Overmars, Efficient motion planning for an L-shaped object, Proceedings of the fifth annual symposium on Computational geometry, p.156-166, June 05-07, 1989, Saarbruchen, West Germany
Martin Tompa, An optimal solution to a wire-routing problem (preliminary version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.161-176, April 28-30, 1980, Los Angeles, California, United States
Wei Lai , Peter Eades, Removing edge-node intersections in drawings of graphs, Information Processing Letters, v.81 n.2, p.105-110, 31 January 2002
W. Gueaieb , F. Karray , S. Al-Sharhan, Computational intelligence based approach for the joint trajectory generation of cooperative robotic systems, Systems Analysis Modelling Simulation, v.42 n.10, p.1499-1520, October 2002
R. Wolfe , W. Fitzgerald , F. Gracer, Interactive graphics for volume modeling, ACM SIGDA Newsletter, v.12 n.2, p.11-18, April 1982
Vladlen Koltun, Pianos are not flat: rigid motion planning in three dimensions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Nadia Magnenat-Thalmann , Daniel Thalmann, Complex Models for Animating Synthetic Actors, IEEE Computer Graphics and Applications, v.11 n.5, p.32-44, September 1991
Kenneth D. Forbus , James V. Mahoney , Kevin Dill, How Qualitative Spatial Reasoning Can Improve Strategy Game AIs, IEEE Intelligent Systems, v.17 n.4, p.25-30, July 2002
K. Sridharan , T. K. Priya, A parallel algorithm for constructing reduced visibility graph and its FPGA implementation, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.10, p.635-644, October 2004
Brian Salomon , Maxim Garber , Ming C. Lin , Dinesh Manocha, Interactive navigation in complex environments using path planning, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California
Karen I. Trovato , Leo Dorst, Differential A*, IEEE Transactions on Knowledge and Data Engineering, v.14 n.6, p.1218-1229, November 2002
Micha Sharir, Algorithmic Motion Planning in Robotics, Computer, v.22 n.3, p.9-20, March 1989
J.-K. Seong , G. Elber , J. K. Johnstone , M.-S. Kim, The convex hull of freeform surfaces, Computing, v.72 n.1-2, p.171-183, April 2004
D. T. Pham , Dayal R. Parhi, Navigation of multiple mobile robots using a neural network and a Petri Net model, Robotica, v.21 n.1, p.79-93, January 2003
A. Paoluzzi , F. Bernardini , C. Cattani , V. Ferrucci, Dimension-independent modeling with simplicial complexes, ACM Transactions on Graphics (TOG), v.12 n.1, p.56-102, Jan. 1993
Ray Jarvis, Robot path planning: complexity, flexibility and application scope, Proceedings of the 2006 international symposium on Practical cognitive agents and robots, November 27-28, 2006, Perth, Australia
Thorsten Bernholt , Friedrich Eisenbrand , Thomas Hofmeister, A geometric framework for solving subsequence problems in computational biology efficiently, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
Gokul Varadhan , Shankar Krishnan , T. V.N. Sriram , Dinesh Manocha, A Simple Algorithm for Complete Motion Planning of Translating Polyhedral Robots, International Journal of Robotics Research, v.25 n.11, p.1049-1070, November 2006
Il Lang Yi , Yuan-Shin Lee , Hayong Shin, Mitered offset of a mesh using QEM and vertex split, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York
Deborah A. Joseph , W. Harry Plantings, On the complexity of reachability and motion planning questions (extended abstract), Proceedings of the first annual symposium on Computational geometry, p.62-66, June 05-07, 1985, Baltimore, Maryland, United States
A. Koutsou, A geometric reasoning system for moving an object while maintaining contact with others, Proceedings of the first annual symposium on Computational geometry, p.67-74, June 05-07, 1985, Baltimore, Maryland, United States
K. Kedem , M. Sharir, An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles, Proceedings of the first annual symposium on Computational geometry, p.75-80, June 05-07, 1985, Baltimore, Maryland, United States
Alonzo Kelly , Anthony Stentz, Rough Terrain Autonomous Mobility—Part 2: An Active Vision, Predictive Control Approach, Autonomous Robots, v.5 n.2, p.163-198, May 1998
Chia-Pin Wu , Tsu-Tian Lee , Chau-Ren Tsai, Obstacle avoidance motion planning for mobile robots in a dynamic environment with moving obstacles, Robotica, v.15 n.5, p.493-510, September 1997
Andreas C. Nearchou , Nikos A. Aspragathos, A genetic path planning algorithm for redundant articulated robots, Robotica, v.15 n.2, p.213-224, March 1997
P. J. de Rezende , D. T. Lee , Y. F. Wu, Rectilinear shortest paths with rectangular barriers, Proceedings of the first annual symposium on Computational geometry, p.204-213, June 05-07, 1985, Baltimore, Maryland, United States
L. Paul Chew, Planning the shortest path for a disc in O(n2log n) time, Proceedings of the first annual symposium on Computational geometry, p.214-220, June 05-07, 1985, Baltimore, Maryland, United States
S. W. Lee , B. H. Lee , K. D. Lee, A configuration space approach to collision avoidance of a two-robot system, Robotica, v.17 n.2, p.131-141, March 1999
Alain Pruski , Serge Rohmer, Robust Path Planning for Non-Holonomic Robots, Journal of Intelligent and Robotic Systems, v.18 n.4, p.329-350, April 1997
Jong Hwan Lim , Dong Woo Choo, Sonar Based Systematic Exploration Method for an Autonomous Mobile Robot Operating in an Unknown Environment, Robotica, v.16 n.6, p.659-667, November 1998
Jin-Liang Chen , Jing-Sin Liu , Wan-Chi Lee, A Recursive Algorithm for On-line Clustering Obstacles Cluttered in Dynamic Environments, Journal of Intelligent and Robotic Systems, v.33 n.2, p.209-230, February 2002
Kao-Shing Hwang , Ming-Yi Ju, Speed Planning for a Maneuvering Motion, Journal of Intelligent and Robotic Systems, v.33 n.1, p.25-44, January 2002
Kao-Shing Hwang , Ming-Yi Ju, 3D Collision-Free Motion Based on Collision Index, Journal of Intelligent and Robotic Systems, v.33 n.1, p.45-60, January 2002
C. Louste , A. Liegeois, Near Optimal Robust Path Planning for Mobile Robots: the Viscous Fluid Method with Friction, Journal of Intelligent and Robotic Systems, v.27 n.1-2, p.99-112, January-February 2000
Chia-Ju Wu, Collision-Free Trajectory Planning for Two Cooperative Redundant Manipulators Using the Minimum-Time Criterion, Journal of Intelligent and Robotic Systems, v.18 n.1, p.17-45, January 1997
Nobuhiro Okada , Tadashi Nagata , Tsutomu Hasegawa, A reliable parts-picking system with an active and multi-sensor visual system, Robotica, v.15 n.6, p.693-700, November 1997
A. C. Nearchou , N. A. Aspragathos , D. P. Sofotassios, Reducing the Complexity of Robot‘s Scene for Faster Collision Detection, Journal of Intelligent and Robotic Systems, v.26 n.1, p.79-89, September 1999
Randeep Singh , Nagaraju Bussa, Path planning using Shi and Karl level sets, Proceedings of the 1st international conference on Robot communication and coordination, October 15-17, 2007, Athens, Greece
Rida T. Farouki , Joel Hass, Evaluating the boundary and covering degree of planar Minkowski sums and other geometrical convolutions, Journal of Computational and Applied Mathematics, v.209 n.2, p.246-266, December, 2007
Menelaos I. Karavelas, Guarding curvilinear art galleries with edge or mobile guards, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York
Yang Wang , David Mulvaney , Ian Sillitoe , Erick Swere, Robot Navigation by Waypoints, Journal of Intelligent and Robotic Systems, v.52 n.2, p.175-207, June 2008
Daniel M. Tracy , W. Randolph Franklin , Barbara Cutler , Franklin T. Luk , Marcus Andrade, Path planning on a compressed terrain, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California
Julien Pettré , Marcelo Kallmann , Ming C. Lin, Motion planning and autonomy for virtual humans, ACM SIGGRAPH 2008 classes, August 11-15, 2008, Los Angeles, California
Xuejian He , Yonghua Chen, Haptic-aided robot path planning based on virtual tele-operation, Robotics and Computer-Integrated Manufacturing, v.25 n.4-5, p.792-803, August, 2009
Menelaos I. Karavelas , Csaba D. Tóth , Elias P. Tsigaridas, Guarding curvilinear art galleries with vertex or point guards, Computational Geometry: Theory and Applications, v.42 n.6-7, p.522-535, August, 2009
Lou Tychonievich , David Zaret , John Mantegna , Robert Evans , Eric Muehle , Scott Martin, A maneuvering-board approach to path planning with moving obstacles, Proceedings of the 11th international joint conference on Artificial intelligence, p.1017-1021, August 20-25, 1989, Detroit, Michigan
Rodney A. Brooks , Tomas Lozano-Perez, A subdivision algorithm in configuration space for findpath with rotation, Proceedings of the Eighth international joint conference on Artificial intelligence, p.799-806, August 08-12, 1983, Karlsruhe, West Germany
C. M. Witkowski, A parallel processor algorithm for robot route planning, Proceedings of the Eighth international joint conference on Artificial intelligence, p.827-829, August 08-12, 1983, Karlsruhe, West Germany
Leo B. Hartman , Josh D. Tenenberg, Performance in practical problem solving, Proceedings of the 10th international joint conference on Artificial intelligence, p.535-540, August 23-29, 1987, Milan, Italy
Boi Faltings, Qualitative kinematics in mechanisms, Proceedings of the 10th international joint conference on Artificial intelligence, p.436-442, August 23-29, 1987, Milan, Italy
Alex Nash , Kenny Daniel , Sven Koenig , Ariel Feiner, Theta*: any-angle path planning on grids, Proceedings of the 22nd national conference on Artificial intelligence, p.1177-1183, July 22-26, 2007, Vancouver, British Columbia, Canada
Subir Kumar Ghosh , Thomas Caton Shermer , Binay Kumar Bhattacharya , Partha Pratim Goswami, Computing the maximum clique in the visibility graph of a simple polygon, Journal of Discrete Algorithms, v.5 n.3, p.524-532, September, 2007

INDEX TERMS

Keywords:
collision-free paths, graph searching, growing objects, path finding, polyhedral objects, polyhedral obstacles

Collaborative Colleagues:
Tomás Lozano-Pérez: colleagues
Michael A. Wesley: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player