Literature
Display
← All papers

Hybrid Declarative-Imperative Representations for Hybrid Discrete-Continuous Decision-Making

Jiayuan Mao · Joshua B. Tenenbaum · Tomás Lozano-Pérez · Leslie Pack Kaelbling

· WAFR 2024 proceedings ↗

Robotics12 min text · CondensedOriginal paper ↗
Contents

At a glance

CDL describes robot behavior using a mixture of direct instructions and choices resolved through planning. Its interpreter, CROW, searches over alternative behaviors, subgoal orders, interleavings, and continuous parameter values. Programmers can restrict these choices or commit to a partial solution when domain structure makes that safe.

The paper contributes a language, an interpreter, navigation-among-movable-obstacles examples, and a connection to planning width. Its empirical study compares three behavior specifications on three illustrative problems. The theoretical results concern stated model and search assumptions; they do not establish general real-world safety or efficient solution of arbitrary hybrid planning problems.

1. Introduction

Robot decisions combine discrete choices—such as which object to move—with continuous grasps, poses, and trajectories. Imperative policies choose actions directly; declarative planners search for actions satisfying a transition model and goal. Different parts of one task can benefit from different amounts of search.

The authors unify these approaches through commitments: whether to search over a subgoal’s method, achievement order, interleaving, or parameter bindings. Behavior rules act as nondeterministic programs that generate candidate action sequences. More freedom improves coverage but usually increases computation.

NAMO examples

Figure 1 compares three navigation strategies [25]. Direct connection chooses a path, moves its obstructing objects away, and traverses it. Waypoint connection clears and traverses path segments in stages. Promotable waypoint connection also allows obstacle-clearing and waypoint subplans to interleave.

The easy instance has enough accessible storage for independent obstacle moves. The medium instance needs a waypoint because the full path cannot be cleared at once. The hard instance requires moving an obstacle needed later before advancing through earlier path segments. The language expresses these differences through small changes in the behavior specification.

Complete original figure 1
Fig. 1: (a)–(c):cdl specifications for three different NAMO solutions; (d)–(f): example problems of different degrees of difficulty. Full programs in Appendix C.

Contributions

The contribution is a common representation spanning hand-written policies, hierarchical planning, and general planning, together with an interpreter that exploits the supplied structure. Assertions check feasibility; ordering and commitment reduce branching. The paper does not introduce a learning procedure for automatically discovering that structure.

2. The Crow Definition Language

A problem comprises a state space, primitive controllers, deterministic transition function, initial state, and goal classifier. This paper assumes full state observability, deterministic transitions, and uniform action costs. A valid controller sequence must obey the transitions and end in a goal state.

CDL generates plans through choices of behavior rules, ordering/interleaving, and free-variable values. Assertions and modeled effects prune invalid plans, while commitment can discard alternatives. The plan space may be infinite when parameters are continuous.

Perception and control interfaces

A state contains a fixed finite universe of typed objects and relational features whose values can be discrete or continuous. External perception code supplies those features. Primitive controllers execute physical sensorimotor routines, such as following a trajectory or attaching to an object, and return control when finished. The exact type, feature, and controller declarations follow.

Complete original code 01
Complete original code 02

Behavior rules

A behavior rule has a name, parameters, a goal condition, and a body. Rules are lifted: the same holding-object rule can apply to any suitable object. Refinement starts from a top-level goal and replaces abstract goals with rule bodies until only primitive controller actions and checks remain.

2.1 Imperative scripting

The simplest program uses let for an external computation, achieve for a subgoal, and do for a primitive controller. With one applicable rule per goal and deterministic bindings, it specifies one hierarchical action sequence, similar to a simple behavior tree [4].

The preserved move-away example approaches an object, attaches, selects storage, moves the object, and detaches. It works only when storage and obstacle interactions meet its assumptions. Without effect models and soundness checks, correctness remains the programmer’s responsibility.

Complete original code 03
Complete original code 04
Complete original code 05
Complete original code 06

2.2 Nondeterminism and soundness

Multiple rules can achieve the same goal through different actions. An assert requires a condition to hold at a plan step, while an effect section updates modeled features. Preconditions may prune search early even when a later goal check would eventually reject the same invalid plan.

The complete RefineS pseudocode recursively replaces the last unresolved achievement with a matching rule, appends its effects, and yields candidate traces. Variable substitution aligns rule parameters with the requested goal.

Complete original algorithm refines
Complete original code 07
Complete original code 08

Internal and external soundness

Projected states change through declared effects; assertions are evaluated against those states. Internal soundness means that all these modeled checks pass. Proposition 1 connects this to external goal achievement only when the plan ends with the goal assertion and the effect statements agree with actual world transitions.

A resettable simulator can supply effects, but the guarantee still depends on that simulator representing the real transitions. The original projected-state equation and proposition are retained below.

Equation
Complete original equation state
Complete original proposition 1

2.3 Subgoal ordering and promotion

Some subgoals can be achieved in either order, and some require interleaving their primitive actions. Opening a cupboard and holding an object illustrates the distinction: retrieving a step stool may have to happen before grasping the object even if opening the cupboard finishes later.

Unordered statement groups

An unordered group leaves statement order to search. A foreach group similarly leaves the order of object-specific work unspecified. Reordering complete subplans is different from interleaving their internal actions.

Complete original code 09

Promotable statement groups

A promotable section permits subgoal refinements to interleave. A rule may place ordinary ordered or unordered work before and after it, preserving serialization where justified. The footnote also allows ordered-but-interleavable statements. This selective flexibility is intended to avoid paying for unrestricted interleaving everywhere.

Plan traces and refinement

Each partially refined program is represented by left, middle, and right sections. The middle is promotable. Refining a middle achievement moves the new rule’s left work into the left section, its right work before the existing right section, and its middle work into the current middle.

Refining outside the middle recursively solves that rule without merging its internals into unrelated subgoals. Figure 2 preserves the graph transformation. Serialization can reduce search exponentially when the problem permits it [20].

Complete original figure 2
Fig. 2: Illustration of how the refinement operator works. Each node corresponds to a statement (or a sequential program). We first nondeterministically select a node in the “middle” section that is the last statement of one of the sequential chains, and then nondeterministically select a behavior to refine it. Finally, we construct a new plan by “inserting” the refined sub-plan to the graph following the rules.

2.4 Variable binding

A bind statement introduces a typed free variable subject to a constraint. Finding grasps, trajectories, or placements becomes a constraint-satisfaction problem [10]. Conditional generators can propose satisfying values—for example, a motion planner can generate trajectories between chosen endpoints.

A variable-augmented trace is sound when some assignment makes the entire trace sound. Binding order suggests a solver order, but the semantics allow any sound solver; completeness depends on whether the solver can actually find the required assignments.

Complete original code 10
Complete original code 11

2.5 Commitment

Commit accepts one feasible partial trace and its associated parameter bindings, discarding alternatives. In the example, the first valid placement for an obstacle is retained without backtracking to other placements, although obstacle order may still be searched.

This can save substantial computation when every local solution is compatible with the remaining task. A misplaced commit can remove the only globally successful choice. It preserves the checks on returned plans but can sacrifice completeness.

Complete original code 12

3. The Crow interpreter

CROW—Compositional Regression and Optimization Wayfinder—maintains the three program sections, free variables, and constraints. It handles left work, then middle work, then right work, recursively refining behaviors and checking deterministic assertions. Unresolved continuous constraints are deferred to the solver.

The original Plan/Crow pseudocode is retained in full, including the commit branch that solves current constraints, fixes one assignment, and stops exploring alternatives. It is mathematical pseudocode, not a tested executable listing; the source contains notation inconsistencies such as an assertion using a differently primed state symbol.

Complete original algorithm crow

Iterative deepening and correctness

A plain depth-first search can follow an unproductive branch indefinitely, so the implementation uses iterative deepening over nested achievements. Theorem 1 states termination with a sound plan when such a plan is generated at finite refinement depth.

This is relative to the supplied behavior specification and successful constraint solving. The paper separately warns that commitment may discard alternatives and that practical continuous sampling is capped. Those restrictions should not be read as a complete solver for every continuous problem. The theorem also does not promise minimum action cost.

Complete original theorem 1

3.1 Problem hardness and runtime

For discrete planning without free continuous bindings, the relevant width bounds how many achievement statements accumulate in the middle and right sections. Theorem 2 relates width K and N entities to an NO(K) search bound, following earlier work [20]. The exact theorem and proof sketch are preserved.

The paper proposes iterative widening to achieve this width-based bound. It does not claim the simple depth-first implementation automatically has that runtime. Small constant width can make scaling polynomial; width that grows with the problem does not provide the same benefit.

Extension to hybrid problems is conditional on a suitable bound for solving continuous constraints. Hard-to-sample feasible values can defeat that assumption. The number of uncommitted continuous variables is another source of exponential cost.

Complete original theorem 2Complete original proof width

3.2 NAMO experiments

The experiment runs each of the three specifications ten times on each of three illustrated NAMO instances. Figure 3 shows cumulative success against wall-clock time. Simpler specifications solve compatible easy problems faster, while additional waypoint and interleaving choices enable harder instances at greater search cost.

The comparison changes the behavior program while retaining the common CROW interpreter. Appendix C limits every method to at most one intermediate waypoint for the comparison. These are three illustrative instances with repeated stochastic runs, not a broad task benchmark or physical-robot evaluation.

Complete original figure 3
Fig. 3: Percentage of successful executions as a function of wall-clock seconds; each plot corresponds to a NAMO problem instance, and each line-color corresponds to a behavior program.

Future work

Proposed learning directions include partial transition models and policies, useful assertions, subgoal ordering, commitment decisions, samplers, and variable ordering [3] [19] [28]. The present paper exposes these choices in a language; it does not evaluate learning them automatically.

Acknowledgements

The authors acknowledge NSF, AFOSR, ONR/MURI, ARO, MIT Quest, MIT–IBM Watson AI Lab, Boston Dynamics AI Institute, ONR Science of AI, and the Simons Center for the Social Brain. Conclusions are attributed to the authors rather than their sponsors.

Appendix A: Refinement rules

Appendix A formalizes the ordering structures and generalized refinement operator used in the main text. All original examples, the tail definition, the full operator, and the completeness proof are retained.

Statement orders

Sequential and unordered groups can nest to express partial orders. The tail operator returns statements that could occur last in a valid serialization; repeatedly choosing from this set enumerates the possible orders. The two-object foreach expansion and exact recursive tail equation follow.

Equation
Complete original equation tail
Complete original code 13
Complete original code 14

Generalized refinement operator

The generalized operator considers possible final statements from the left, middle, or right. A middle achievement merges its child sections with the surrounding program; other achievements are recursively refined and concatenated. The complete Refine pseudocode preserves all cases.

CDL separates generation of candidate traces from assertions/effects that test them. Exhaustive generation followed by testing is possible in principle but can be inefficient or incomplete in continuous domains. Incremental checks and other search strategies can exploit partial structure.

Complete original algorithm refine

A.1 Completeness and soundness proof

The proof argues that CROW’s left-first traversal enumerates the same refinements as the abstract operator at a fixed depth. It factors refinement into left, middle, and right components and proves the factorization by induction over the selected tail statement. Increasing the depth then covers any finite-depth solution. The complete proof, including both displayed identities and all three induction cases, is preserved below.

Complete original proof completeness

Appendix B: Constraint satisfaction

Constraints must refer to the state at the time they were generated. The implementation uses time-indexed fluents: assigning a feature from unresolved inputs introduces a new variable and an equation linking that variable to the inputs. This converts state-dependent evaluation into pure constraints that a solver can process.

Complete original code 15
Complete original code 16

B.1 Sampling-based solver

The sampling solver follows earlier task-and-motion planning work [10]. It propagates determined Boolean values, evaluates functions whose inputs are fixed, and removes an equality when its otherwise-unused output can be ignored. It then branches over remaining discrete values before invoking continuous generators.

Generators declare constraints and input/output roles. A matching constraint with known inputs supplies samples for unknown outputs. The practical implementation caps samples per generator, so absence of a sampled solution does not prove that no continuous solution exists.

Complete original code 17

Appendix C: NAMO implementation

The full 64-line NAMO program includes recursive waypoint selection, a base case, obstacle relocation, approach, and object transport. After moving an obstacle, the move-away behavior also returns the robot to its prior location. Both pages of the original listing are retained with line numbers, comments, and indentation.

Complete original code 18
Complete original code 19

NAMO generators and experimental settings

The six generators choose a waypoint not directly reachable from the starting state, connect endpoints while ignoring movable obstacles, propose a free object location, approach an object, connect robot poses collision-free, and move a robot–object pair. Several use randomized grid A* searches.

They depend on current object and robot locations. Reachability constraints can fail implicitly when a generator cannot produce an assignment. The free-location sampler first reasons about object reachability without requiring robot reachability; subsequent constraints must resolve the full motion. Experiments cap intermediate waypoints at one.

Appendix D: CDL manual

The manual explains object-centered representations, data-oblivious computation, typed features, external functions, generators, effects, and complete examples. The original source code is retained throughout.

D.1 Object-centered representation

Features and behaviors are parameterized by objects, making one representation applicable to different object counts. The examples define a scalar position feature and a controller-backed rule that changes it.

Complete original code 20
Complete original code 21

Data-oblivious computation

Data-oblivious computation has a control/data-access structure determined by input size rather than feature values, with value operations encapsulated in primitives. Bounded loops and finite-universe quantification can be expanded in advance; value-dependent unbounded recursion cannot.

The manual contrasts a fixed five-step movement program with a value-dependent while loop. It separates these restrictions on internal function/effect computation from the behavior-refinement recursion used by the planner. Externally implemented primitives can contain more general computation.

Complete original code 22
Complete original code 23

D.2 Types and features

The entity universe is fixed and finite for each problem. Bounded creation can be modeled with preallocated hypothetical entities, and deletion with a feature. Object types differ from value types: objects admit finite-universe quantification, while unrestricted continuous values generally do not.

The exact declarations show inheritance, scalar and vector values, external Python objects, and typed relational features.

Complete original code 24
Complete original code 25
Complete original code 26
Complete original code 27
Complete original code 28

D.3 Functions

Primitive functions have external implementations; derived functions compose features and other functions in CDL. Supported constructs include feature access, Boolean operations, finite quantifiers, arithmetic, local assignments, conditionals, and parallel object loops.

Derived functions must remain data-oblivious. The preserved mutually recursive example is explicitly invalid. Loop-body assignments cannot mutate an outer local variable. All original syntax examples are retained.

Complete original code 29
Complete original code 30
Complete original code 31
Complete original code 32
Complete original code 33
Complete original code 34
Complete original code 35

D.4 External functions and generators

External primitives may be non-oblivious. To support backward reasoning through them, a generator declares inputs, outputs, and a condition guaranteed by generated values. The inverse-function example returns x and y satisfying a specified value of f(x,y).

Complete original code 36

D.5 Behavior effects

An effect program updates relational features. Restricting its internal computation makes it possible to translate the forward update into a descriptive precondition/effect representation. The exact Hoare-style formula and bounded-loop translation are preserved.

The accompanying seventeen-line PDDL-style result spans two source pages; both parts are retained. These examples illustrate the compilation idea and should be read as printed notation rather than silently corrected executable code.

Equation
Complete original equation hoare
Complete original code 37
Complete original code 38
Complete original code 39

D.6 Ordering example

The cupboard example combines unordered prerequisites, a computed placement, repeated cup placement, and final closure. It demonstrates how one behavior can mix ordering commitments at different levels.

Complete original code 40

Blocks-world program and Sussman anomaly

The complete 112-line blocks-world listing defines features, primitive controllers, and behaviors for holding, clearing, emptying the hand, stacking, and placing on the table. All three pages and the original indentation are preserved.

Figure 4 retains the complete Sussman-anomaly refinement trace and mathematical caption [26]. It illustrates how promotion interleaves subgoal work that a purely sequential rule decomposition would miss.

The listing is reproduced as printed, including the holding-variable assignment in the unstack rule and other syntax inconsistencies. It is evidence of the proposed representation, not a claim that this PDF transcription has been executed or verified as an implementation.

Complete original figure 4
Figure 4. Original refinement diagram and complete original mathematical caption.
Complete original code 41
Complete original code 42
Complete original code 43
Concept demonstration

Open image ↗