Markov Decision Processes in Artificial Intelligence

Chapter 15

Operations Planning 1

15.1. Operations planning

This chapter deals with the application of MDPs to operations1 planning problems. Such problems arise in areas ranging from space exploration (rovers, satellites, telescopes) to project management and military operations. Automated planning [GHA 04, REG 04] is a branch of Artificial Intelligence. It aims at building general-purpose systems capable of choosing and organizing the operations to perform, in such a way as to reach given objectives at least cost. Here, we examine complex planning problems. These not only require concurrent operation execution and the explicit modeling of time and operation durations. They also make it necessary to account for uncertainty about the effects of operations and about the time at which they occur. Such problems are known as probabilistic temporal planning problems [ABE 06, ABE 07b, LIT 05, MAU 05, MAU 07]. We define them in an intuitive way before providing a formal definition. We then focus on their modeling as an MDP and on their resolution using variants of algorithms presented in the previous chapters.

15.1.1. Intuition

We start with an intuitive presentation of the problem illustrated by a space exploration example. In our scenario, a Mars rover must carry out several experiments on various sites and acquire scientific data which it must transmit to Earth [BRE 02] (see also Chapter 14).

15.1.1.1. Problem features

An operations planning problem is characterized by:

– an environment ...