Time-Critical Planning and Scheduling in Stochastic Domains (Extended Abstract)

) Thomas L. Dean Lloyd Greenwald Leslie Pack Kaelbling Jak Kirman Ann Nicholson Department of Computer Science Brown University, Box 1910, Providence, RI 02912 In this note we summarize our recent work on time-critical decisionmaking under uncertainty. Our research has resulted in a family of algorithms that extend techniques in artificial intelligence and operations research to efficiently handle stochastic processes with very large state and/or action spaces. In the traditional AI planning perspective the world is assumed to be deterministic and planning is done entirely off-line. Plans are made far in advance of execution with idealized expectations of the target situation; plans go wrong and are patched by humans with incomplete, local knowledge resulting in drastically sub-optimal performance. Traditional methods in operations research and combinatorial optimization either fail to account for uncertainty and time pressure or employ only simple predictive models. Even the best of..