Planning with deadlines in stochastic domains

Thomas Dean, Leslie Pack Kaelbling, Jak Kirman, Ann Nicholson

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

69 Citations (Scopus)


We provided a method, based on the theory of Markov decision problems, for efficient planning in stochastic domains. Goals are encoded as reward functions, expressing the desirability of each world state; the planner must find a policy (mapping from states to actions) that maximizes future rewards. Standard goals of achievement, as well as goals of maintenance and prioritized combinations of goals, can be specified in this way. An optimal policy can be found using existing methods, but these methods are at best polynomial in the number of states in the domain, where the number of states is exponential in the number of propositions (or state variables). By using information about the starting state, the reward function, and the transition probabilities of the domain, we can restrict the planner's attention to a set of world states that are likely to be encountered in satisfying the goal. Furthermore, the planner can generate more or less complete plans depending on the time it has available. We describe experiments involving a mobile robotics application and consider the problem of scheduling different phases of the planning algorithm given time constraints.

Original languageEnglish
Title of host publicationProceedings of the National Conference on Artificial Intelligence
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages6
ISBN (Print)0262510715
Publication statusPublished - 1 Dec 1993
Externally publishedYes
EventAAAI Conference on Artificial Intelligence 1993 - Washington, United States of America
Duration: 11 Jul 199315 Jul 1993
Conference number: 11th


ConferenceAAAI Conference on Artificial Intelligence 1993
Abbreviated titleAAAI 1993
CountryUnited States of America

Cite this