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.
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.
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.
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.
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
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.
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].
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.
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.
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.
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.
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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).
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
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.
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.