Extending real-time heuristic search Part Ⅰ: Dynamically-changing goal sets

摘要

Real-time search methods are an efficient tool for agents with limited sensing capabilities that are interacting with an initially unknown environment. They allow the agent to gradually discover the search space, while simultaneously searching for the goal. The aim of this work is to extend these search methods to previously unaddressed frameworks. The focus in Part Ⅰ of this paper is on the problem of searching for a set of goals that can change dynamically during the search process. The proposed solution makes use of multiple heuristic estimates each associated to a goal state to keep track of distances to all goals. It will be first shown that the additional stored information can be used to improve the performance even when the goal set is static just by changing the tie breaking strategy. DMHLRTA~* (Dynamic Multi-Heuristic Learning Real-Time A~*), a search algorithm for dynamically-changing goal sets is then presented. The algorithm allows multiple goals to be added, or removed from the goal set online and without reinitializing the existing heuristic estimates by adding or removing the corresponding heuristic vector elements. The experimental analysis shows that DMHLRTA~* outperforms LRTA~* (Learning Real-Time A~*) and RTA~* (Real-Time A~*) both with heuristics reinitialization, especially for large and highly dynamic goals sets. DMHLRTA~* will be used in Part Ⅱ of this paper as part of a real-time search algorithm for heterogeneous agents.