Path planning for moving a point object amidst unknown obstacles in a plane: a new algorithm and a general theory for algorithm development
- 1 January 1990
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1111-1119 vol.2
- https://doi.org/10.1109/cdc.1990.203773
Abstract
A new algorithm Alg2 is developed to solve the problem of nonheuristically moving a point object (MA) between two given points, amidst unknown obstacles in a plane. The existing algorithms to solve this are Bug1 and Bug2 (J. Lumelsky and A.A. Stepanov, 1987) and Alg1 (A. Sankaranarayanan and M. Vidyasagar, 1990). The existing algorithms make MA follow mostly the contours of the obstacle boundaries. Under Alg2, MA follows the obstacles boundaries less and travels more along straight line segments towards the target point. The worst case path length, convergence, local cycle creation, etc. of Alg2 are presented along the examples of its operation. Alg2 is developed step by step, by adding new procedures to a certain primitive algorithm. This algorithm development brings out the basic requirements of a nonheuristic path planning algorithm, and this knowledge leads to a general algorithm Gen of which the algorithms Bug2, Alg1, and Alg2 are particular cases. This generalization helps understand the basic operating principles of a nonheuristic path planning algorithm.Keywords
This publication has 8 references indexed in Scilit:
- A new path planning algorithm for moving a point object amidst unknown obstacles in a planePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Dynamic path planning for a planar articulated robot arm moving amidst unknown obstaclesAutomatica, 1987
- Effect of kinematics on motion planning for planar robot arms moving amidst unknown obstaclesIEEE Journal on Robotics and Automation, 1987
- Dynamic path planning for a mobile automaton with limited information on the environmentIEEE Transactions on Automatic Control, 1986
- Real-Time Obstacle Avoidance for Manipulators and Mobile RobotsThe International Journal of Robotics Research, 1986
- Continuous motion planning in unknown environment for a 3D cartesian robot armPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Obstacle Avoidance for Kinematically Redundant Manipulators in Dynamically Varying EnvironmentsThe International Journal of Robotics Research, 1985
- Some Heuristics for the Navigation of a RobotThe International Journal of Robotics Research, 1985