Gridworlds as Testbeds for Planning with Incomplete Information

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 17

Planning and Scheduling

Gridworlds are popular testbeds for planning with incomplete information but not much is known about their properties. We study a fundamental planning problem, localization, to investigate whether gridworld make good testbeds for planning with incomplete information. We find empirically that greedy planning methods that interleave planning and plan execution can localize robots very quickly on gridworlds with random obstacles. Thus random gridworlds may not provide adequately challenging testbeds. On the other hand, we show that finding localization plans that are within a log factor of optimal is NP-hard. Thus there are instances of gridworlds on which all greedy planning methods perform very poorly, and we show how to construct them. These theoretical results help empirical researchers to select appropriate planning methods as well as testbeds to demonstrate them.