- Post Doctoral
MIT Unit Affiliation:
- Electrical Engineering & Computer Science
Post Doc Sponsor / Advisor:
Date PhD Completed:
Top 3 Areas of Expertise:
Expected End Date of Post Doctoral Position:
Domain-independent planning is one of the foundational areas in the field of Artificial
Intelligence (AI). A planning task consists of an initial
world state, a goal, and a set of actions for modifying the world state, with the
objective of finding a plan that transforms the initial world state
into a goal state. In cost-optimal planning, we are interested in finding not
just any valid plan, but a cheapest such plan.
One of the most prominent approaches to cost-optimal planning these days is
heuristic state-space search, guided by a heuristic which estimates the distance
from each state to the goal.
Most heuristics for domain-independent planning are what we call classical ---
they estimate the distance from some given state to the goal using only
properties of the given state. In this work, we explore non-classical
heuristics --- heuristics which exploit additional information gathered during
search. We propose a mathematical model which allows us to formally define
non-classical heuristics, as well as a useful taxonomy of heuristics along
several dimensions. We then describe two different classes of non-classical
heuristics: landmark-based heuristics, and machine-learning based heuristics.
Our empirical evaluation shows that non-classical heuristics are not just an
interesting theoretical possibility, but rather state of the art tools in
heuristic search planning.