LEARNING AND APPROXIMATE DYNAMIC PROGRAMMING Scaling Up to the Real World
ion level: traversal abstraction level: primitiveion level: primitive Fig. 1.13 A hierarchical suffix memory state estimator for a robot navigation task. At the abstract (navigation) level, observations and decisions occur at intersections. At the lower (corridor-traversal) level, observations and decisions occur within the corridor. At each level, each agent constructs states out of its past experience with similar history (shown with shadows). Partially observable MDPs are theoretically more powerful than finite memory models, but past work on POMDPs has mostly studied “flat” models for which learning and planning algorithms scale poorly with model size. We have developed a new hierarchical POMDP framework termed H-POMDPs (see Figure 1.14) [42], by extending the hierarchical hidden Markov model (HHMM) [7] to include rewards, multiple entry/exit points into abstract states and (temporally extended) actions. H-POMDPs can also be represented as Dynamic Bayesian networks [43], in a similar way that HHMMs can be represented as DBNs [23]. Figure 1.15 shows a Dynamic Bayesian net representation of H-POMDPs. This model differs from the model described in [23] in two basic ways: the presence of action nodesA, and the fact that exit nodes X are no longer binary. In the particular navigation example shown in Figure 1.14, the exit nodeXt can take on five possible values, representing no-exit, north-exit, east-exit, south-exit, and west-exit. If Xt = no-exit, then we make a horizontal transition at the concrete level, but the abstract state is required to remain the same. If Xt 6= no-exit, then we enter a new abstract state; this abstract state then makes a vertical transition into a new CONCURRENCY, MULTIAGENCY, AND PARTIAL OBSERVABILITY 19 Fig. 1.14 State transition diagram of a hierarchical POMDP used to model corridor environments. Large ovals represent abstract states; the small solid circles within them represent entry states, and the small hollow circles represent exit states. The small circles with arrows represent production states. Arcs represent non-zero transition probabilities as follows: Dotted arrows from concrete states represent concrete horizontal transitions, dashed arrows from exit states represent abstract horizontal transitions, and solid arrows from entry states represent vertical transitions.