Introduction to Discrete Feasible Planning

• • 1. Problem Formulation

The discrete feasible planning model will be defined using state-space models, which will appear repeatedly throughout this book. Most of these will be natural extensions of the model presented in this section. The basic idea is that each distinct situation for the world is called a state, denoted by x, and the set of all possible states is called a state space, X. For discrete planning, it will be important that this set is countable; in most cases it will be finite. In a given application, the state space should be defined carefully so that irrelevant information is not encoded into a state (e.g., a planning problem that involves moving a robot in France should not encode information about whether certain light bulbs are on in China). The inclusion of irrelevant information can easily convert a problem that is amenable to efficient algorithmic solutions into one that is intractable. On the other hand, it is important that X is large enough to include all information that is relevant to solve the task.

The world may be transformed through the application of actions that are chosen by the planner. Each action, u, when applied from the current state, x, produces a new state, x′, as specified by a state transition function, f. It is convenient to use f to express a state transition equation,

x′ = f(x, u). (2.1)

Let U(x) denote the action space for each state x, which represents the set of all actions that could be applied from x. For distinct x, x′ X, U(x) and U(x′) are not necessarily disjoint; the same action may be applicable in multiple states. Therefore, it is convenient to define the set U of all possible actions over all states:

∈

U = U(x). (2.2)

I

x∈X

As part of the planning problem, a set XG X of goal states is defined. The task of a planning algorithm is to find a finite sequence of actions that when ap-

⊂

plied, transforms the initial state xI to some state in XG. The model is summarized as:

Formulation 2.1 (Discrete Feasible Planning)

• • • 1. A nonempty state space X, which is a finite or countably infinite set of states.
      2. For each state x ∈ X, a finite action space U(x).
      3. A state transition function f that produces a state f(x, u) X for every x X and u U(x). The state transition equation is derived from f as x′ = f(x, u).

∈ ∈

∈

• • • 1. An initial state xI ∈ X.
      2. A goal set XG ⊂ X.

It is often convenient to express Formulation 2.1 as a directed state transition graph. The set of vertices is the state space X. A directed edge from x X to x′ X exists in the graph if and only if there exists an action u U(x) such that x′ = f(x, u). The initial state and goal set are designated as special vertices in the graph, which completes the representation of Formulation 2.1 in graph form.

∈ ∈

∈

• • 1. Examples of Discrete Planning

Example 2.1 (Moving on a 2D Grid) Suppose that a robot moves on a grid in which each grid point has integer coordinates of the form (i, j). The robot takes discrete steps in one of four directions (up, down, left, right), each of which increments or decrements one coordinate. The motions and corresponding state transition graph are shown in Figure 2.1, which can be imagined as stepping from tile to tile on an infinite tile floor.

This will be expressed using Formulation 2.1. Let X be the set of all integer pairs of the form (i, j), in which i, j Z (Z denotes the set of all integers). Let U = (0, 1), (0, 1), (1, 0), ( 1, 0) . Let U(x) = U for all x X. The state transition equation is f(x, u) = x + u, in which x X and u U are treated as two-dimensional vectors for the purpose of addition. For example, if x = (3, 4) and u = (0, 1), then f(x, u) = (3, 5). Suppose for convenience that the initial state is xI = (0, 0). Many interesting goal sets are possible. Suppose, for example, that XG = (100, 100) . It is easy to find a sequence of actions that transforms the state from (0, 0) to (100, 100).

∈ ∈

{ }

{ − − } ∈

∈

The problem can be made more interesting by shading in some of the square tiles to represent obstacles that the robot must avoid, as shown in Figure 2.2. In this case, any tile that is shaded has its corresponding vertex and associated edges deleted from the state transition graph. An outer boundary can be made to fence

in a bounded region so that X becomes finite. Very complicated labyrinths can be constructed. ．

Figure 2.1: The state transition graph for an example problem that involves walk- ing around on an infinite tile floor.

Example 2.2 (Rubik’s Cube Puzzle) Many puzzles can be expressed as dis- crete planning problems. For example, the Rubik’s cube is a puzzle that looks like an array of 3 3 3 little cubes, which together form a larger cube as shown in Figure 1.1a (Section 1.2). Each face of the larger cube is painted one of six colors. An action may be applied to the cube by rotating a 3 3 sheet of cubes by 90 degrees. After applying many actions to the Rubik’s cube, each face will generally be a jumble of colors. The state space is the set of configurations for the cube (the orientation of the entire cube is irrelevant). For each state there are 12 pos- sible actions. For some arbitrarily chosen configuration of the Rubik’s cube, the planning task is to find a sequence of actions that returns it to the configuration

×

× ×

Figure 2.2: Interesting planning problems that involve exploring a labyrinth can be made by shading in tiles.

in which each one of its six faces is a single color. ．

It is important to note that a planning problem is usually specified without explicitly representing the entire state transition graph. Instead, it is revealed incrementally in the planning process. In Example 2.1, very little information actually needs to be given to specify a graph that is infinite in size. If a planning problem is given as input to an algorithm, close attention must be paid to the encoding when performing a complexity analysis. For a problem in which X is infinite, the input length must still be finite. For some interesting classes of problems it may be possible to compactly specify a model that is equivalent to Formulation 2.1. Such representation issues have been the basis of much research in artificial intelligence over the past decades as different representation logics have been proposed; see Section 2.4 and [382]. In a sense, these representations can be viewed as input compression schemes.

Readers experienced in computer engineering might recognize that when X is finite, Formulation 2.1 appears almost identical to the definition of a finite state machine or Mealy/Moore machines. Relating the two models, the actions can be interpreted as inputs to the state machine, and the output of the machine simply reports its state. Therefore, the feasible planning problem (if X is finite) may be interpreted as determining whether there exists a sequence of inputs that makes a finite state machine eventually report a desired output. From a planning perspective, it is assumed that the planning algorithm has a complete specification of the machine transitions and is able to read its current state at any time.

Readers experienced with theoretical computer science may observe similar connections to a deterministic finite automaton (DFA), which is a special kind of finite state machine that reads an input string and makes a decision about whether to accept or reject the string. The input string is just a finite sequence of inputs, in the same sense as for a finite state machine. A DFA definition includes a set of accept states, which in the planning context can be renamed to the goal set. This makes the feasible planning problem (if X is finite) equivalent to determining whether there exists an input string that is accepted by a given DFA. Usually, a language is associated with a DFA, which is the set of all strings it accepts. DFAs are important in the theory of computation because their languages correspond precisely to regular expressions. The planning problem amounts to determining whether the empty language is associated with the DFA.

Thus, there are several ways to represent and interpret the discrete feasible planning problem that sometimes lead to a very compact, implicit encoding of the problem. This issue will be revisited in Section 2.4. Until then, basic planning algorithms are introduced in Section 2.2, and discrete optimal planning is covered in Section 2.3.

(a) (b)

Figure 2.3: (a) Many search algorithms focus too much on one direction, which may prevent them from being systematic on infinite graphs. (b) If, for example, the search carefully expands in wavefronts, then it becomes systematic. The re- quirement to be systematic is that, in the limit, as the number of iterations tends to infinity, all reachable vertices are reached.