page 1 page 2 page 4 page 5

Simulated Annealing for Robot Inverse Kinematics (page 3)

Annealing describes a process of heating a material to an elevated temperature and then cooling it slowly. The slow cooling allows the material to reach a low energy state in which it is ductile. With no intelligence or systematic strategy, some materials minimize energy state during the slow cooling. Simulated annealing models this process on a computer. The model is based on the Boltzmann probability distribution. In this equation, E is the energy of the system, k is Boltzmann's constant, and T is the temperature. Essentially, Boltzmann states that a system's energy probabilistically distributes depending upon the temperature. As the temperature increases, the probability of the system assuming a higher energy state increases. As the temperature decreases, the probability of the system leaving a lower energy state decreases. Each configuration option corresponds to an energy state. Because simulated annealing algorithms sometimes leave lower energy states for higher ones, they can escape from local minima. Simulated annealing algorithms typically include a method of generating random changes in the system's configuration. The random changes represent trial configurations evaluated using the Boltzmann probability distribution. If the distribution indicates, the system assumes the trial configuration; otherwise it is discarded.

In the configuration advisor application, a single set of joint displacements is one trial configuration. The algorithm generates the displacements for the redundant joints (five for the DAWM) randomly and then solves for the remaining joint displacements (twelve for the DAWM) using inverse kinematics. Performance criteria values associated with the trial configuration are the equivalent of energy in the algorithm. The example application calculates the energy as the weighted sum of two elementary criteria, though continuing work is investigating more sophisticated criteria fusion schemes. One of the criteria measures the approach to joint travel limits and the other criteria measures the approach to collisions. If the trial exceeds a travel limit or would result in a collision, the algorithm rejects the configuration immediately.

Van Doren and Tesar (1992) have formulated and implemented in software over 30 performance criteria. These criteria emphasize task-based performance indicators derived from the physical description of the manipulator. These formulations emphasize efficiency and portability. Available computing power makes decisions based on several of these criteria possible in real-time. Given the rapid pace of advancements in computational speed, it will soon be possible to employ the entire suite of performance criteria in a real-time decision making process. Table 2. lists the general categories of these performance criteria. Continuing work focuses on issues of normalization and multiple criteria fusion.

Elementary physical limitations form the basis for the constraint criteria. These limitations restrict joint travels, joint speeds, joint accelerations, and joint torques. The joint travel availability is a representative criterion that seeks to keep the joint displacements as near as possible to the midpoints of their travel.

The Jacobian matrix forms the basis for the geometric performance criteria. These criteria are
task independent and based only on the geometry of the robot, thus these criteria are formulated once for each robot with no need for reformulation if the task changes (Cleary and Tesar, 1990).