Publications Details

Adaptive path planning for incrementally-changing environments

Chen, P.C.

Path planning needs to be fast to facilitate real-time robot programming. Unfortunately, current planning techniques are still too slow to be effective, as they often require several minutes, if not hours of computation. To overcome this difficulty, we present an adaptive algorithm that uses previous experience to speed up future performance. It is a learning algorithm suitable for incrementally-changing environments such as those encountered in manufacturing of evolving products and waste-site remediation. The algorithm extends our previous work for stationary environments in two directions: For minor environmental change, an object-attached experience abstraction scheme is introduced to increase the flexibility of the learned experience; for major environmental change, an on-demand experience repair scheme is also introduced to retain those experiences that remain valid and useful. In addition to presenting this algorithm, we identify three other variants with different repair strategies. To analyze the respective performance of these algorithms, we develop an analytic model that quantifies and relates training effort, experience value and utility, and environmental change through intuitive terms of energy and work. It is a general and simple model that should be very useful in characterizing other types of learning processes as well. Using this model, we formalize the concept of incremental change, and prove the optimality of our proposedalgorithm under such change. Empirically, we also characterize the performance curve of each variant, confirm our theoretical optimality results, and demonstrate the practicality of our algorithm.