On Planning while Learning

This paper introduces a framework for Planning while Learning where an agent is given a goal to achieve in an environment whose behavior is only partially known to the agent. We discuss the tractability of various plan-design processes. We show that for a large natural class of Planning while Learning systems, a plan can be presented and verified in a reasonable time. However, coming up algorithmically with a plan, even for simple classes of systems is apparently intractable. We emphasize the role of off-line plan-design processes, and show that, in most natural cases, the verification (projection) part can be carried out in an efficient algorithmic manner. 1. Introduction Suppose you find yourself in a complex labyrinth, with no recollection as to what brought you there or how to get out. You do have some knowledge as to the possible outcomes of your actions (e.g., gravitation works as usual). However, several basic characteristics of your surrounding are unknown (e.g., the map of th..