A unique task in artificial intelligence is the problem of navigating an idealized robot arm (a series of connected line segments) from a starting position to an ending position while avoiding obstacles in its path. One technique that can be used to solve this problem is the beam search. Consider a single position of the robot arm that is advanced by making a random adjustment to one of the angles of the arm segments. The beam search independently tracks between ten and fifty of these robot arm positions. After each random movement, a probabilistic objective function is used to determine which positions will continue to be tracked. By assigning a higher probability of survival to those positions that are closer to the ending position, the robot arm can make forward progress. This process is continued until one of the tracked positions reaches the ending position. A major challenge to this technique is in devising an objective function that consistently selects robot arm positions that are closer to the end position. Our beam search quickly solves most data sets with up to twenty angles and four obstacles. Solutions were reached in about 5,000 to 20,000 moves.
David Baur, ’09 Boulder, CO
Majors: Computer Science, Mathematics
Raine Lourie, ’08 West Rupert, VT
Major: Computer Science
Sponsor: Andrew Wildenberg