Adaptive path planning in changing environments

摘要

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 compare these algorithms, we develop an analytic model to compare the costs and benefits of the corresponding repair processes. Using this model, we formalize the concept of incremental change, and prove the optimality of our proposed algorithm 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.