Value-Update Rules for Real-Time Search

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Scheduling

Real-time search methods have successfully been used to solve a large variety of search problems but their properties are largely unknown. In this paper, we study how existing real-time search methods scale up. We compare two real-time search methods that differ only in the update rules of their values and have been used successfully in the literature: Node Counting, a real-time search method that always moves to the successor state that it has visited the least number of times so far, and Learning Real-Time A*, a subtly different real-time search method. Both real-time search methods seemed to perform equally well in standard domains from artificial intelligence and robotics. Our formal analysis is therefore very surprising. We show that the performance of Node Counting can be exponential in the number of states even in undirected domains. This solves an open problem from the literature and shows that the two real-time search methods do not always perform similarly in undirected domains since the performance of Learning Real-Time A* is known to be polynomial in the number of states at worst.