Task Scoping: Generating Task-Specific Abstractions for Planning
  A generally intelligent agent requires an open-scope world model: one rich
enough to tackle any of the wide range of tasks it may be asked to solve over
its operational lifetime. Unfortunately, planning to solve any specific task
using such a rich model is computationally intractable - even for
state-of-the-art methods - due to the many states and actions that are
necessarily present in the model but irrelevant to that problem. We propose
task scoping: a method that exploits knowledge of the initial condition, goal
condition, and transition-dynamics structure of a task to automatically and
efficiently prune provably irrelevant factors and actions from a planning
problem, which can dramatically decrease planning time. We prove that task
scoping never deletes relevant factors or actions, characterize its
computational complexity, and characterize the planning problems for which it
is especially useful. Finally, we empirically evaluate task scoping on a
variety of domains and demonstrate that using it as a pre-planning step can
reduce the state-action space of various planning problems by orders of
magnitude and speed up planning. When applied to a complex Minecraft domain,
our approach speeds up a state-of-the-art planner by 30 times, including the
time required for task scoping itself.
