target). Note that since Per(R 1 ) N R 1 = 0, all the policies defined in this manner have deterministic stopping conditions.

Let the set of all policies defined be Π 1 . At the higher level P 2 , for each region R 2 ,
we can define a set of policies that model the agent's behaviours inside that region with applicable state space R 2 , destination set Per(R 2 ), and the constraint that these policies must use the policies previously defined at level-1 to achieve their goals. An example is a policy to navigate between the room-doors to get from one building gate to another. Let the set of all policies defined at this level be H2. Continuing doing this at the higher levels, we obtain the policy hierarchy H = ( Π 0 , Π 1 , Π 2 , . . , Π K ). A policy hierarchy constructed through State-space Region-based Decomposition is termed an SRD policy hierarchy.

An SRD policy hierarchy has the property that the set of applicable states of all the policies at a given abstraction level forms a partition of the state space. Thus, from the state sequence ( so, the exact starting and terminating times of all intermediate-level policies. For example, at level k , the starting/stopping times of the policies in this level are the time indices t's at which the state sequence crosses over a region boundary: s t − 1 ∈ R k and s t ̸ Q R k for some region R k of the partition P k . Later in section 5.1, we will show that this property helps to simplify some of the complexity of the policy recognition problem.

## 3.3  A Policy Hierarchy Example

As an example, consider the task to monitor and predict the movement of an agent through a building shown in Fig. 5(a). Each room is represented by a 5 × 5 grid, and two adjacent rooms are connected via a door in the center of their common edge. The four entrances to the building are labeled north (N), west (W), south (S) and east (E). In addition, the door in the center of the building (C) acts like an entrance between the building's north wing and south wing. At each state (cell), the agent can move in 4 possible directions except when it is blocked by a wall.

The policy hierarchy to model the agent's behaviour in this environment can be constructed based on region-based decomposition at three levels of abstraction.  Firstly, a region hierarchy is constructed. The partition of the environment consists of the 8 rooms at level 1, the two wings (north and south) at level 2, and the entire building at level 3.  The behaviours of the agent at level 1 (within each room) is represented by a set of level 1 policies. For example, in each room, we use 4 level-1 policies to model the agent's behaviours of exiting the room via the 4 different doors.  These are essentially four Markov chains within the room which terminate outside of the room.  One way to represent these policies is to specify which movement action the agent should take given the current position and the current heading. At the higher level, the agent's behaviours within each wing are specified. For example, we use 3 level-2 policies in each wing to model the agent's behaviours of exiting the wing via the 3 wing exits. These policies are built on top of the set of level-1 policies already defined. They specify which level-1 policies the agent should take to leave the wing at the intended exit. Finally, at the top level, the agent's behaviours within the entire building can be specified. For example, we use 4 top-level policies to model the agent's behaviours of leaving the building via the four building exits N, W, S, E. A sample of these policies and their parameters is given in Fig. 5(b).