Selective Abstraction in Automated Planning

One of the most studied areas of human reasoning from a computational point of view has been planning. Classical Automated Planning (AP) deals with the generation of ordered sets of actions that, when correctly executed, allow an agent (or set of agents) to transit from an initial state to a final state where a set of goals are satisfied. We are interested on building intelligent systems that sense, reason (plan) and execute plans in the real world. Since most real environments are stochastic and/or dynamic, we focus on planners that handle the extra complexity of considering non-determinism and/or dynamism. Currently, the two major approaches to deal with these envi-ronments consist on explicit reasoning on probabilistic domain models, or, in the other extreme, reasoning only with full deterministic models (removing all probabilistic information), execution of generated plans, and replanning when needed. In this paper, we propose a variation of the second approach. Our technique, Variable Resolution Planning (VRP), performs a detailed analysis of the near future (first actions in the plan). After a given planning horizon, it abstracts away details as it reasons about the far future. The advantages of this approach are that it: is faster than regular full-fledged planning (both in the probabilistic or deterministic settings); does not spend much time on the far future possibilities that will not be reached anyway, since in most cases it will need to replan before finding the end of the plan; takes into account some main components of the far future (as an improvement over pure reactive systems); and, from a cognitive perspective, plausibly is closer to how humans plan in these kinds of environments. 1