Robot Path Planning via Simulated Annealing: A Near Real Time Approach

Abstract

Abstract An efficient procedure for near optimal robot path planning in a two dimensional workplace is presented. Obstacles are represented as a series of rectangular regions which allows collision detection to be performed by an operation similar to clipping in computer graphics. The feasible design space is approximated by a discrete set of robot arm and gripper positions. A control sequence of the angular position of each link is determined. A set of intermediate link positions are generated and grouped into stages. A dynamic programming problem is formulated to locate the best state within each stage which minimizes the overall path length. A simulated annealing solution procedure is implemented in order to locate a reasonable solution in the minimum amount of time. Several examples are presented involving a three link planar manipulator. Extensions to three dimensional robot path planning and real time control in a dynamically changing workplace are discussed.