Hierarchical Lookahead Agents A Preliminary Report分层超前剂初步报告.ppt

Hierarchical Lookahead Agents:A Preliminary Report Bhaskara Marthi Stuart Russell Jason Wolfe High-level actions For our purposes, a high-level action (HLA) Has a set of possible immediate refinements into sequences of actions, primitive or high-level Each refinement may have a precondition on its use Many of the actions we do are high-level Go to work Write a NIPS paper This definition generalizes others we’ve seen Options don’t provide a choice of refinements MAXQ tasks can’t represent sequencing constraints Abstract Lookahead k-step lookahead 1-step lookahead e.g., chess k-step lookahead no use if steps are too small e.g., first k characters of a NIPS paper this is one small part of a human life, = ~20,000,000,000,000 primitive actions Angelic semantics for HLAs Models HLAs in deterministic domains without rewards Central idea is reachable set of an HLA from some state When extended to sequences of actions, allows proving that a plan can or cannot possibly reach the goal May seem related to nondeterminism But the nondeterminism is angelic: the “uncertainty” will be resolved by the agent, not an adversary or nature Contributions Extended angelic semantics to account for rewards Developed novel algorithms that do lookahead Hierarchical Forward Search An optimal, offline algorithm Can prove optimality of plans entirely at high level Hierarchical Real-Time Search An online algorithm Requires only bounded computation per time step Significantly outperforms previous ``flat’’ lookahead algorithms Both algorithms require three inputs: a deterministic MDP model an action hierarchy (HLAs) models for HLAs (based on angelic semantics) Deterministic MDPs A deterministic MDP consists of: State space S Initial state s0 2 S, (w.l.o.g.) single terminal state t ? S Primitive action set A Transition function f : S x A ! S Reward function r : S x A ! R Undiscounted, assume no non-negative-reward cycles Example – Warehouse World Has similarities to blocks and taxi domains