PaperlayerView exact revision on arXiv

Source-linked AI summary

CAMPs: Learning Context-Specific Abstractions for Efficient Planning in Factored MDPs

Rohan Chitnis, Tom Silver, Beomjoon Kim, Leslie Pack Kaelbling, Tomas Lozano-Perez

arXiv:2007.13202v3cs.LGcs.AIcs.RO

TL;DR

Planning during sequential decision-making can be computationally burdensome. The paper learns contexts that induce abstractions of factored MDPs, then plans in those CAMPs; experiments report advantages over most baselines, with a classical-planning exception.

  • Problem

    Online planning is computationally burdensome, while choosing constraints to guide planning must balance reward against computation and may sacrifice optimality.

    Source: §1 · p. 1

  • Method

    The method learns a context selector, uses selected contexts to form context-specific abstractions of factored MDPs, and plans in the resulting CAMPs.

    Source: §1 · p. 1, §3 · p. 4, §4.2 · p. 6

  • Results

    CAMPs outperform every baseline except in classical-planning Domain D2, and consistently have lower computational costs than pure planning across the experiments.

    Source: §5.3 · p. 7

  • Takeaways & Limitations

    The paper concludes that learned CAMPs offer a promising path toward fast, effective planning in large and challenging domains.

    Source: §7 · p. 8

    CAMPs are usually not optimality-preserving because imposing a context restricts the agent to a subregion of the state and action space.

    Source: §3 · p. 4

Abstract

from arXiv · show

Meta-planning, or learning to guide planning from experience, is a promising approach to improving the computational cost of planning. A general meta-planning strategy is to learn to impose constraints on the states considered and actions taken by the agent. We observe that (1) imposing a constraint can induce context-specific independences that render some aspects of the domain irrelevant, and (2) an agent can take advantage of this fact by imposing constraints on its own behavior. These observations lead us to propose the context-specific abstract Markov decision process (CAMP), an abstraction of a factored MDP that affords efficient planning. We then describe how to learn constraints to impose so the CAMP optimizes a trade-off between rewards and computational cost. Our experiments consider five planners across four domains, including robotic navigation among movable obstacles (NAMO), robotic task and motion planning for sequential manipulation, and classical planning. We find planning with learned CAMPs to consistently outperform baselines, including Stilman's NAMO-specific algorithm. Video: https://youtu.be/wTXt6djcAd4 Code: https://git.io/JTnf6

1 Introduction

The paper proposes CAMPs, which use self-imposed constraints to create context-specific independences and remove irrelevant variables for planning. It learns which contexts to impose to balance reward and computational cost.

1 Introduction

  • CAMPs abstract a factored MDP by imposing a context and removing variables made irrelevant by the resulting context-specific independences.For example, restricting the robot to certain rooms can make obstacles in forbidden rooms irrelevant.Source: §1 · p. 1
  • The objective trades off highly rewarding behavior against computational burden, accepting possible suboptimality and, for goal-based tasks, loss of soundness or completeness.The paper proposes learning-based context selection to optimize this trade-off.Source: §1 · p. 1
  • The method approximates task-relevant context-specific independences, trains a context selector on training tasks, then uses its selected context to form a CAMP for test-time planning.The selector predicts a context for a novel task from its task features.Source: §1 · p. 2
  • The approach rests on the premise that predicting a context is easier to generalize than learning a reactive policy, because a context need only preserve a region containing a good path.A reactive policy must carve out a specific good path through transition space.Source: §1 · p. 2
  • Across four domains and multiple planners, the reported results suggest CAMPs balance pure planning and policy learning; in NAMO, they outperform Stilman’s specialized algorithm.The domains include NAMO and sequential manipulation, and collectively cover discrete and continuous states and actions, relational states, sparse rewards, stochastic transitions, and long planning horizons.Source: §1 · p. 2

2 Preliminaries

The preliminaries introduce the MDP and factored-MDP setting, define context-specific independence, and formulate test-task planning as a trade-off between reward and computational cost.

2 Preliminaries

  • The paper introduces its background formalism before defining the planning problem.The preliminaries comprise notation and background formalism, followed by the problem definition.Source: §2 · p. 2

2.1 Context-Specific Independence in Factored Markov Decision Processes

  • In a factored MDP, state and action assignments comprise variables, and context-specific independence captures conditional independence under a specified context.The paper explores automatically identifying and exploiting these independences for planning.Source: §2.1 · pp. 2–3

2.2 Problem Formulation

  • Tasks share the factored state and action spaces, transition model, and horizon, while each task is specified by an initial state and reward function.The task representation is featurized, and the analytical forms of the transition and reward functions are unknown to the agent.Source: §2.2 · p. 3
  • The objective values a policy by expected cumulative reward minus λ times its computational cost, including computation before acting and during execution.The cost may be wall-clock time, and λ controls the reward-cost trade-off.Source: §2.2 · p. 3
  • Planning in the full test MDP may be computationally costly, while transferring a task-conditioned reactive policy may reduce test-time cost at the expense of reward if it fails to generalize.These alternatives motivate the reward-computation trade-off formalized in the objective.Source: §2.2 · pp. 3–4

3 Context-Specific Abstract Markov Decision Processes (CAMPs)

CAMPs abstract a factored MDP by retaining variables relevant within a chosen context, enabling planning with a trade-off between computational cost and reward. Because a context can restrict the state-action region, the resulting policy is usually not guaranteed to preserve optimality.

3 Context-Specific Abstract Markov Decision Processes (CAMPs)

  • A projective abstraction maps states and actions to abstract spaces by retaining selected variables and dropping the rest.The projections drop n−n′ state variables and m−m′ action variables.Source: §3 · p. 4
  • Context-specific relevance drops variables that cannot influence reward under the given context, generalizing relevance that holds across contexts.The relevant-variable projection can be too restrictive because many variables may influence reward under some action sequence.Source: §3 · p. 4
  • A CAMP uses the context-specific projection to define an abstract MDP, with context-violating transitions leading to a sink state with reward −∞.The sink is absorbing; arbitrary values may be assigned to dropped variables when applying the right inverses.Source: §3 · p. 4
  • CAMPs are usually not optimality-preserving because a context restricts the agent to a subregion of the state and action space.Context-specific relevance is weaker than general relevance: for example, outdoor weather can be irrelevant while a robot remains indoors.Source: §3 · p. 4
  • For a test MDP, the agent selects a context, computes relevant variables, builds a CAMP, and plans in it to obtain a policy.The data-flow diagram distinguishes learning the selector on training tasks from applying it to a test task.Source: §3 · p. 5, Figure 3 · p. 5

4 Learning to Generate CAMPs

The method learns approximate context-specific independences and a context selector, then uses them to generate CAMPs for planning on test tasks.

4 Learning to Generate CAMPs

  • The method learns approximate context-specific independences and a context selector for use in generating CAMPs at test time.The section's pipeline uses both learned components to construct an abstraction for a test task.Source: §4 · p. 5

4.1 Approximating the Context-Specific Independences

  • The sample-based CSI procedure tests empirical dependence between pairs of state or action variables, conditioned on sampled values of the remaining variables.It examines whether sampled values of one variable change the distribution of another at the next timestep.Source: §4.1 · p. 5
  • CSI discovery runtime depends on domain size and sample count, and identifying all independences could require arbitrarily many samples.For the robotic manipulation and NAMO tasks considered, the algorithm detected useful independences and was robust to errors, which at worst exclude candidate abstractions.Source: §4.1 · p. 5
  • The candidate context family uses conjunctions and disjunctions up to a length limit, excludes terms below a joint-domain-size threshold, and includes the universal context.For any finite threshold, this procedure excludes contexts involving continuous variables; other, more domain-specific context families may also be used.Source: §4.1 · p. 5

4.2 Learning the Context Selector

  • For each training task, a neural network learns to predict the best context from task features using cross-entropy loss.The predicted context is used at test time to generate a CAMP and plan for the task.Source: §4.2 · p. 6

5 Experiments and Results

The experiments compare learned CAMPs with planning and policy-learning baselines across four domains and examine planner generality, λ sensitivity, and training-task count. CAMPs generally offer a favorable reward–computation trade-off, with results varying by domain.

5 Experiments and Results

  • The experiments ask whether CAMP performance generalizes across varied domains, depends on planner choice, changes with λ, or improves with more training tasks.The domains include discrete and continuous settings.Source: §5 · p. 6

5.1 Domains and Planners

  • Evaluation spans four domains and five planners, including gridworld, classical planning, NAMO, and sequential manipulation, using MCTS, Fast-Downward, and TAMP among the planners.Gridworld also uses BFSReplan and value iteration; the sequential-manipulation domain uses the NAMO task-and-motion planner.Source: §5.1 · p. 6

5.2 Methods and Baselines

  • Baselines include pure planning, plan transfer, policy learning, task-conditioned policy learning, a context-only CAMP ablation, and a NAMO-specific planner.In these domains, pure planning can also be viewed as CAMP without contexts because every variable is relevant under no context.Source: §5.2 · pp. 6–7

5.3 Main Results

  • CAMPs outperform all baselines except in D2; across experiments they use less computation than pure planning and sometimes earn higher rewards in NAMO and manipulation.Figure 4 compares mean returns with computation time; its points average 10 independent training and evaluation runs.Source: Figure 4 · p. 7, §5.3 · p. 7
  • Imposing contexts alone focuses planning on promising search regions, while additionally dropping irrelevant variables provides greater benefits.The context-only CAMP ablation sends context violators to a sink state but does not project away irrelevant variables.Source: §5.3 · p. 7
  • In NAMO, CAMPs perform comparably to Stilman’s NAMO-specific algorithm, with the learned selector favoring emptier rooms and often reaching goals faster.CAMPs move comparatively few objects and obtain higher rewards than Stilman’s algorithm because they often reach the goal faster.Source: §5.3 · pp. 7–8

5.4 Performance as a Function of λ

  • As λ increases in classical planning, CAMP returns interpolate from pure-planning returns toward random-policy returns, while CAMP objective values never fall below the random policy’s.At high λ, the context selector chooses contexts that induce little planning, but returns are low.Source: §5.4 · p. 8

6 Related Work

Related work situates CAMPs among experience-guided planning, MDP abstraction, and CSI-based planning. CAMPs learn contexts that induce structured abstractions for efficient planning.

6 Related Work

  • Prior meta-planning learns policies, value functions, or constraints from planning experience; CAMPs instead predict contexts, while other constraint-prediction methods can be incorporated into the framework.Prior work also uses contexts to represent instances in score space but does not consider the resulting CSIs.Source: §6 · p. 8
  • MDP abstraction work includes state-action aggregation and learned abstraction selection; CAMP contexts induce a structured hypothesis space of abstractions for efficient planning.State-action aggregation generalizes projective abstractions.Source: §6 · p. 8
  • CAMPs and CSI-based planning methods such as SPUDD are complementary: SPUDD considers all contexts, whereas CAMPs learn a context selector that induces abstractions.The paper notes that the approaches could be integrated for further efficiencies.Source: §6 · p. 8

7 Conclusion

The conclusion presents learned context-specific abstractions as a way to plan more efficiently while retaining high rewards, and identifies extensions involving learned factorizations, task features, and successive contexts. The appendices describe learning approximate context-specific independences and a context selector, while Figure 5 illustrates how imposed contexts produce a CAMP.

7 Conclusion

  • The method learns context-specific abstractions to achieve more efficient planning while retaining high rewards; future work includes learning factorizations and task features, and imposing contexts successively despite added cost.The task featurizer is assumed given, and successive contexts could increase computational cost, possibly hurting the overall objective.Source: §7 · p. 8

A Pseudocode: Approximate Context-Specific Independence Learning

  • The approximate-CSI procedure samples within a context and tests variable pairs for dependence to identify approximate context-specific independences.The pseudocode initializes variable pairs as independent, then removes pairs when dependence is detected.Source: A Pseudocode: Approximate… · p. 12

B Pseudocode: Context Selector Learning

  • The context selector is trained as a classifier from task features to objective-best contexts, using CAMP planning to score candidate contexts.The pseudocode specifies cross-entropy loss for supervised learning.Source: B Pseudocode: Context Selector Learning · p. 12

C CAMP Graphical Example

  • Figure 5 shows how imposing a context can induce an independence, make variables irrelevant, and yield a CAMP by dropping those variables.In the example, imposing a context involving S2 makes S2 and S3 independent, with A2 and S3 irrelevant; relevance is time-independent.Source: C CAMP Graphical Example · p. 12, Figure 5 · p. 13

D Domain and Planner Details

The domain details span gridworld and classical planning as well as robotic NAMO and sequential manipulation. Their task variations, relevant constraints, and planners differ across these settings.

Domain D1: Gridworld

  • Gridworld tasks vary maze layouts; restricting rooms lets the agent ignore obstacles there and their removal actions, with 50 training and 10 held-out tasks.The agent navigates around stochastically moving obstacles, and collisions return it to its initial location.Source: D Domain and Planner Details · p. 13

Domain D2: Classical planning

  • Classical planning varies meal rewards across 20 training and 25 held-out tasks; the deterministic domain uses Fast-Downward in A* mode with lmcut.Ramen, sandwich, and steak options have different rewards and planning lengths; the task has a timestep penalty.Source: D Domain and Planner Details · pp. 13–14

Domain D3: Robotic navigation among movable obstacles (NAMO)

  • NAMO varies object positions across 50 training and 10 held-out tasks, with continuous geometry making planning challenging; it uses a task-and-motion planner with RRT-Connect and Fast-Forward PDDL.The robot may avoid entering rooms or move obstacles; reaching the goal earns 1000 under a sparse reward.Source: D Domain and Planner Details · p. 14

Domain D4: Robotic sequential manipulation

  • Sequential manipulation varies object positions, occupied bins, and red-object radii across 50 training and 10 held-out tasks; grasp-style or bin constraints can make distractors irrelevant.Top-grasping can avoid blue objects but is not always feasible; side-grasping is needed for upright placement, and regrasping can simplify planning.Source: D Domain and Planner Details · pp. 14–15

E Experimental Details

Experiments measure computational cost in wall-clock time and apply domain- and planner-specific settings for the objective, planning timeout, networks, and candidate contexts.

E Experimental Details

  • Experiments use horizon H = 25 and λ values of 0 for MCTS, 100 for BFSReplan, 250 for FastDownward, and 100 for TAMP; γ = 0.99 except in Domain D2.Domain D2 instead uses a timestep penalty.Source: E Experimental Details · p. 15
  • Planning calls time out after 60 seconds because completing every method can be extremely slow, including pure planning or a poor selected context.The timeout safeguards evaluation of the objective in Equation 1.Source: E Experimental Details · p. 15
  • Networks use fully connected or convolutional architectures, while candidate contexts use discrete variables and domain-specific constraint forms and k1, k2 settings.The fully connected layers are [50, 32, 10]; convolutional networks use 10 channels and kernel size 2, followed by pooling and fully connected layers.Source: E Experimental Details · p. 15

F Performance as a Function of Number of Training Tasks

In Domain D2, CAMP outperforms policy learning with few training tasks, while policy learning does better with all 20 tasks. The authors report a stronger CAMP advantage in the other three, more varied domains.

F Performance as a Function of Number of Training Tasks

  • With ≤8 training tasks, CAMP outperforms policy learning in Domain D2, but policy learning performs better with all 20 tasks.The plots show objective value and returns as a function of training-task count.Source: F Performance as a Function of Number… · p. 15
  • In the other three, more varied domains, CAMPs sharply outperform policy learning for any reasonable number of training environments tested.The authors suggest CAMPs may be more viable when data is limited in domains where policy learning does well with more data.Source: F Performance as a Function of Number… · p. 16

G Objective Values for Main Experiments

Table 1 complements Figure 4 by reporting objective values across all domains, planners, and methods, using the λ values selected during training.

G Objective Values for Main Experiments

H Performance with an Offline Planner

With asynchronous value iteration on D1 gridworld test tasks, CAMPs strongly outperform pure policy learning and pure planning. State-space reduction benefits offline planning, which must find a policy over the entire state space.

H Performance with an Offline Planner

  • The offline-planner test reports objective values for D1 gridworld tasks using asynchronous value iteration.Source: H Performance with an Offline Planner · p. 16
  • CAMPs strongly outperform pure policy learning and pure planning with the offline planner, reflecting generalization error and high computational cost, respectively.CAMP’s reduced state space benefits offline planners that find policies over the entire state space.Source: H Performance with an Offline Planner · p. 16
Loading 2007.13202v3…