PaperlayerView exact revision on arXiv

Source-linked AI summary

APTree: Extended Behavior Trees for Adaptive and Scalable Automated Robotic Task Planning in Construction

Shermin Sherkat, Thomas Wortmann, Andreas Wortmann

arXiv:2610.18523v1cs.ROcs.AIcs.SE

TL;DR

Task planning for construction prefabrication is largely manual, and existing approaches have limited support for scalable modular planning and localized replanning. APTree coordinates symbolic planners through a behavior-tree-based framework with a DSL and execution engine; in a real-world pavilion case study, it modeled and validated the domain and generated an assembly plan using three planners.

  • Problem

    Construction robotic fabrication planning is typically manual, while existing approaches offer limited support for scalable modular task planning and localized runtime replanning.

    Source: §1 · pp. 1–2

  • Method

    APTree uses a planner-independent model-driven framework to coordinate symbolic planners and compose validated task-plan modules into behavior-tree execution models through a DSL and compatible engine.

    Source: §1 · p. 2

  • Results

    In the livMatS Biomimetic Shell case study, APTree modeled and validated the CRF domain and generated the assembly plan using ENHSP, Metric-FF, and LAMA-First.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The DSL and execution engine let domain users focus on the planning problem rather than low-level planner and behavior-tree implementation details.

    Source: §1 · p. 2

    The verification methods reviewed are mainly limited to small behavior trees or individual subtrees, without automatic analysis of dependencies across large trees.

    Source: §3.1 · p. 7

Abstract

from arXiv · show

Task planning for robots in off-site construction prefabrication is primarily manual, leading to planning inefficiencies and reluctance to adopt robotic solutions. Existing approaches provide limited support for scalable, modular automated task planning and localized runtime replanning. This paper proposes APTree, a model-driven framework that integrates automated task planning with modular task execution using behavior trees as the execution model. APTree repeatedly applies and coordinates heterogeneous symbolic planners to automatically generate and compose modular task plans at runtime. To support this approach, we develop a domain-specific language for the formal specification and validation of task plans, together with a compatible execution engine. We evaluate APTree on the real-world livMatS Biomimetic Shell pavilion, where it models the construction robotic fabrication domain, detects injected specification and planning errors at design time and runtime, and automatically generates large-scale task plans by coordinating three symbolic planners across numerous planning modules. A machine-checked formal analysis further shows that composed execution and local replanning are safe under explicitly stated assumptions, including planner soundness and non-interference of generated plans, providing practitioners with explicit conditions for dependable plan composition. APTree thus enables construction practitioners to leverage automated task planning without requiring detailed knowledge of symbolic planning techniques or APTree's internal implementation.

1. Introduction

APTree addresses manual and poorly scalable construction-robotic-fabrication planning with a model-driven framework that coordinates symbolic planners and composes modular plans into behavior-tree execution models. Its DSL, execution engine, and livMatS case study demonstrate the approach’s specification, validation, and planning workflow.

1. Introduction

  • CRF planning involves hundreds of heterogeneous tasks, objects, resources, and constraints, while current manual planning is inefficient and existing approaches have gaps in dependencies, localized replanning, and scalability.The identified challenges include hidden dependencies that can cause runtime errors, rigid replanning structures, and brittle execution models as planning problems grow.Source: §1 · pp. 1–2
  • APTree coordinates symbolic planners to generate task-plan modules, validates and transforms them into its DSL, then composes them into a behavior tree supporting localized runtime replanning.The planner-independent abstraction allows planners to be applied repeatedly at different levels of granularity.Source: §1 · p. 2
  • Its extended BT metamodel covers domain types, graph-based task plans, and planning services, while the DSL and compatible execution engine support validation, planner invocation, and modular planning.Only the composition into the executable model and the execution engine are BT-specific.Source: §1 · p. 2
  • In the livMatS Biomimetic Shell case study, APTree modeled and validated the CRF domain and generated the segment-assembly plan using ENHSP, Metric-FF, and LAMA-First.The pavilion’s shell segments were robotically fabricated off-site before on-site assembly.Source: §1 · p. 3

2. Background and Terminology

This section introduces behavior-tree execution, model-driven engineering and software-language concepts, MontiCore, and symbolic and sub-symbolic planning. These concepts provide the terminology and background for APTree’s modeling and planning framework.

2.1. Behavior Trees and The Running Example

  • Behavior trees execute tasks through ticked action and control-flow nodes, using sequence, fallback, or parallel logic; decorators can check node-specific preconditions before execution.The running example sequences plate pickup and placement before executing two beam tasks in parallel.Source: §2.1 · p. 4, Figure 2 · p. 4

2.2. Model-Driven Engineering and Software Languages

  • Model-driven engineering uses purpose-built models to reduce complexity; software languages define model syntax and runtime behavior, while language constraints specify structural or behavioral well-formedness rules.Abstract syntax captures concepts and relationships, whereas concrete syntax specifies how users express them.Source: §2.2 · pp. 4–5

2.3. MontiCore

  • MontiCore supports modular text-based DSLs by generating infrastructure from grammars, and its symbols and well-formedness rules enable model validation.A PickUp production can require a referenced name to correspond to an existing Beam instance.Source: §2.3 · p. 5

2.4. AI Task Sequence Planning Paradigms: Symbolic and Sub-symbolic

  • Symbolic planners reason over explicit states, actions, preconditions, and effects to construct action sequences toward a goal; sub-symbolic planners instead learn policies from data to select actions sequentially.PDDL separates general domain definitions from concrete problem instances.Source: §2.4 · p. 6

3. Research Challenges and Related Work

The related work identifies three challenges for modular task execution: managing hidden data dependencies, replacing plans locally at runtime, and generating executable plans scalably. It reviews symbolic and sub-symbolic approaches and their limitations in addressing these challenges.

3.1. Type Mismatches and Hidden Dependencies (C1)

  • Implicit data sharing and undeclared interfaces can produce type conflicts, side effects, and execution failures when independently developed task models are composed.Existing verification methods are mainly limited to small BTs or individual subtrees, rather than analyzing dependencies across large BTs.Source: §3.1 · p. 7

3.2. Limited Support for Localized Task Plan Replacement (C2)

  • Runtime changes may invalidate only part of a CRF plan, but existing execution languages offer limited localized replacement and may require restructuring or regenerating the whole model.The cited challenge also notes that such changes can lead to state loss.Source: §3.2 · pp. 7–8

3.3.1. Symbolic AI Planners

  • Symbolic approaches include HTN-based BT generation and back-chaining, but planner-determined structure can make trees brittle and planner coupling can limit generalization across paradigms.PlanSys2 generates executable BTs from PDDL-based planner output but is tightly coupled to the underlying planner representation.Source: §3.3.1 · pp. 8–9

3.3.2. Sub-symbolic AI Planners

  • Sub-symbolic BT-generation methods include language models, learning, genetic algorithms, and case-based reasoning, but lack accurate plan verification and can perform worse as task counts increase.Their performance also depends substantially on training-data quality, which can compromise consistency and flexibility in unpredicted situations.Source: §3.3.2 · p. 9

3.3. Limited Automated Generation of Execution Models (C3)

  • Automated execution-model generation remains difficult to scale: sub-symbolic generation is described as unreliable, while symbolic planners can face combinatorial explosion and yield brittle models.The identified open challenge is scalable, modular plan generation that can be reliably transformed into execution models.Source: §3.3 · p. 8, §3.3.2 · p. 9

4. Research Questions and Evaluation Goals

Using the Goal–Question–Metric method, the section defines evaluation questions and metrics for error detection, local replanning, and scalable automated execution-model generation.

4.1. Error Detection of Task Execution Models

  • For Q1–Q4, true positive rate measures injected errors detected across design, planning, and runtime, while prevention rate measures errors prevented by design.The evaluated errors include structural, typing, syntactic, and logical inconsistencies; errors classified as not applicable are excluded.Source: §4.1 · pp. 10–11

4.2. Support for Local Task Replanning

  • For Q5, structural change combines relative changes in BT size, breadth, and depth; lower values indicate greater structural preservation after replanning.For Q6, replanning frequency and node-retention rate quantify runtime modifications sustained in a single run, not task outcomes or recovery performance.Source: §4.2 · p. 11

4.3. Scalable and Robust Automated Execution Model Generation

  • Q7–Q8 assess whether multiple symbolic planners can be composed and large planning problems decomposed, using planner diversity, application count, latency, and decomposition metrics.Planner diversity counts distinct planners successfully invoked; application count tracks planning and replanning applications.Source: §4.3 · p. 12
  • Q7 also measures the number of distinct planners used and total planning or replanning applications during one execution.Higher values indicate stronger support for heterogeneous planners and repeated autonomous planning in independently executed modules.Source: §4.3 · p. 12
  • Q9 evaluates logical correctness by checking preserved task dependencies and ordering, while Q10 measures latency between consecutive action executions.Logical correctness does not require exact action-name or plan-length matches.Source: §4.3 · p. 12
  • For Q8, planner latency includes invocation, model transformation, and plan integration; decomposition factor captures executed planning steps contributed per submodule.Lower decomposition-factor values indicate finer decomposition across planning submodules.Source: §4.3 · p. 12

5. APTree Domain Specific Language

The section describes APTree’s DSL packages for specifying syntax, well-formedness, and behavior across behavior-tree execution, domain types, and planning services. It explains how configurable dynamic flow nodes represent planner-generated subplans as partially ordered graphs, separate plan structure from execution semantics, and define execution, success reporting, and replanning recovery.

5.1. Behavior Tree DSL Package

  • The BT DSL defines a root flow node, flow and leaf action nodes, decorators, and services, with unique names and structural rules expressed in MontiCore syntax.Flow nodes may contain children, action nodes cannot, and the first node is designated Root.Source: §5.1 · p. 13
  • A BT node tick evaluates services, decorators, and node logic; Sequence ticks children left to right, while Parallel ticks all children and flow nodes derive status from child outcomes.Services and decorators use type-specific evaluation logic, and decorators can modify the returned status during post-processing.Source: §5.1 · p. 14
  • BT execution uses one shared key–value blackboard and Success, Failure, InProgress, Uninitialized, and ReadyToTick statuses, with ticks restricted to eligible nodes.A node is finished only when its last status is Success or Failure.Source: §5.1 · pp. 14–15

5.2. Domain Types DSL Packages

  • DomainTypesDef and DomainTypesCon model task properties, planning preconditions, and effects, enabling interface checks, runtime validation, and generated domain-specific grammars.DomainTypesDef defines abstract types; DomainTypesCon instantiates them as concrete types for different robotic fabrication domains.Source: §5.2 · pp. 15, 17
  • CustomProperty supertypes distinguish agents, elements, locations, tools, and organizational or textual types, while predicate references define action preconditions and effects using action properties.Separating predicates from action properties allows planning assumptions to be validated independently during composed plan execution.Source: §5.2 · pp. 15–16
  • Three action levels separate deterministic high-level design intent from adaptive mid-level planning and fine-grained low-level execution, with subtree references constrained by hierarchy.High-level actions may reference mid-level subtrees, mid-level actions may reference low-level subtrees, and low-level actions cannot reference subtrees.Source: §5.2 · pp. 16–17
  • APTree models world states as predicates on a blackboard, checks action preconditions against that state, and applies action effects after successful execution.Its two-phase input process incrementally parses property, predicate, and action types, generates grammars and C# types, then validates BT models and serializes instances for execution; runtime plans are validated when generated.Source: §5.2 · pp. 18–19

5.3. Planning Service DSL Package

  • Planning services specify and validate planner configurations, invoke external planners, transform returned plans into APTree models, and validate them before execution.When a problem file is absent or mid- or low-level replanning is needed, the service can generate one from blackboard state and higher-level action effects as goals.Source: §5.3 · pp. 20, 22

5.4. Dynamic Flownode DSL Package

  • Dynamic flow nodes represent complete task plans as directed graphs, separating task-plan structure from the execution semantics that orchestrate planning, replanning, and execution.Each node uses configurable logic, may contain children of only one type (AllAction or AllFlow), and must define exactly one success criterion, such as All, Any, Count, or Percentage.Source: §5.4 · pp. 22–23
  • NodeGraph encodes execution order and unconstrained concurrency, with temporal types specifying relations such as Meets while leaving execution logic to flow nodes.This lets a planner-generated subplan be encapsulated in one DynamicFlowNode; nodes without ordering relations need no separate parallel flow node.Source: §5.4 · p. 23
  • APTree extends the base BehaviorTree metamodel, and its DSL grammar provides a complete textual model while requiring dynamic flow nodes and planning services for non-root action-bearing nodes.The running example is presented as a complete APTree DSL model.Source: §5.4 · p. 23
  • Flow nodes evaluate child results against configured success criteria, while getExecutableNodes and canExecute select graph nodes whose predecessor and temporal conditions permit execution.For example, under a Meets constraint, a successor may execute only after its predecessor completes.Source: §5.4 · p. 24, Figure 11 · p. 25
  • A child failure triggers replanning rather than immediate flow-node failure; completed nodes become inactive, unticked nodes may be removed, and new active nodes can be appended.The flow node returns Failure only after the maximum replanning attempts are reached without success; inactive nodes do not count toward success criteria.Source: §5.4 · p. 25

6. Case Study: livMatS Biomimetic Shell Pavilion Prefabrication Process

The livMatS case study models robotic cassette prefabrication and uses APTree to specify planning inputs, generate plans, and coordinate their execution. Its two execution configurations compare cost-driven local replanning with balanced branch progression without replanning.

6. Case Study: livMatS Biomimetic Shell Pavilion Prefabrication Process

  • The pavilion task plans cover three batches of four cassettes, each assembled from six beams and two plates using an industrial robot and interchangeable end-effectors.The robot handles picking and placing, mechanical fastening, and adhesive bonding.Source: §6 · p. 25

6.1. APTree Usage for the livMatS Pavilion

  • APTree users provide domain types, predicates and initial state, action types, planner files, and an initial BT with three batch branches containing four cassette branches each.The case study manually develops two PDDL domain files and 12 initial problem files, one per cassette.Source: §6.1 · pp. 25–26
  • The model loader validates input against the DSL, registers valid types and instances on the blackboard, and starts BT execution; invalid input returns errors.Planner failures or generated models that violate DSL constraints are reported and pause execution.Source: §6.1 · p. 27
  • APTree alternates planning mode, which generates plan nodes through planner services, with action-execution mode, which executes generated actions or expands them into mid-level plans.ENHSP handles high-level planning; Metric-FF and LAMA-First are available for mid-level classical planning, with ENHSP and Metric-FF used unless stated otherwise.Source: §6.1 · p. 27
  • With replanning, CostEvaluation selects the executable branch with the lowest estimated action count, then reset removes obsolete subtrees and triggers planning from the updated world state.Without replanning, FairProgress balances branch progression; Lock makes each selected mid-level subtree execute atomically in both configurations.Source: §6.1 · pp. 27–28

7. Evaluation Using Case Study Results

The evaluation tests APTree’s error handling, replanning, planner coordination, decomposition, plan quality, and runtime behavior against the livMatS case study and PlanSys2. APTree solves larger decomposed problems than the monolithic comparison and reports localized replanning, valid task plans, and stable per-call planning latency.

7. Evaluation Using Case Study Results

  • Across injected errors, APTree’s TPR was 76% versus PlanSys2’s 25%; PlanSys2 prevented 36.8% of errors by design, compared with APTree’s 10%.APTree detected all injected logical errors at runtime; half were resolved automatically and half halted execution.Source: §7 · p. 29
  • Across 1,098 replans, APTree’s average tree-structure change was 0.80% and average width change was 0.38%, while its execution hierarchy remained six levels deep.The structural change per replan is bounded by the replanned mid-level subtree; PlanSys2 regenerates its entire BT when replanning.Source: §7 · p. 29
  • All 372 high-level tasks reached their goals, all 1,098 replanning calls returned valid plans, and no planner or action failures occurred.Actions in this setup always return success once ticked, so these outcomes assess plan generation and composition rather than physical performance.Source: §7 · p. 29
  • APTree coordinated ENHSP, Metric-FF, and LAMA-First across execution, automatically generating 1,470 planning instances with replanning and 372 without, from 12 initial problem files.PlanSys2 invokes one planner once for the complete execution.Source: §7 · p. 30
  • Average per-call latency remained stable across 1,482 replanning-configuration calls: approximately 360 ms with ENHSP and Metric-FF, or 1,746 ms when LAMA-First was added.The reported cumulative planning latency was 65.9% with ENHSP and Metric-FF under replanning, and 89.9% when half of the mid-level planners were LAMA-First.Source: §7 · pp. 30–31, Figure 15 · p. 32
  • At P3 and P4, PlanSys2 ran out of memory while APTree solved both; at P0–P1 PlanSys2 was faster, and at P2 its 5.7 s exceeded APTree’s 3.0 s.APTree automatically decomposed each problem into mid-level subproblems, but the comparison does not establish intrinsic scalability under matched decompositions.Source: §7 · p. 32, Figure 16 · p. 33
  • APTree’s 1,149-node executed plan comprised 372 planning submodules, a decomposition factor of 3.1; it preserved all required steps and ordering and reduced the sequential-execution SSR from 42% to 0%.The two proposed execution policies both achieved the 0% SSR.Source: §7 · pp. 32–33
  • Average consecutive-action latency was 383 ms without replanning and 1,028 ms with replanning, with no cumulative execution overhead from repeated planning.Higher latency occurred at inter-branch transitions: 706 ms without replanning and 2,207 ms with replanning; the paper attributes the longer runtime to repeated symbolic planning.Source: §7 · p. 33

8. Discussion

The discussion presents APTree as a modular framework for automated planning and execution, with a typed DSL connecting planning and execution semantics. The case study demonstrates planner coordination and localized replanning, while identifying limits in evaluation scope, manual configuration, and established progress guarantees.

8. Discussion

  • The full-scale case study demonstrates design-time detection of structural, syntactic, and typing errors, runtime detection of logical errors, localized replanning, and composed task execution models.The DSL integrates validation, planning, replanning, and execution in one framework.Source: §8 · pp. 33–34

8.1. Result Analysis

  • A typed DSL shared by planning and execution preserves planning semantics, enabling design-time detection of structural, syntactic, and typing errors and runtime detection of logical errors.The comparison reports PlanSys2’s two-stage architecture at 0% TPR for both typing and logical errors; those errors instead manifest as runtime failures.Source: §8.1 · p. 34
  • Runtime logical-error detection combines precondition and effect checks against world state with invariants that prevent completed high-level goals from being undone.Invariant 1 violations make a valid plan impossible and terminate execution; runtime violations of Invariant 3 lead to replanning or a full stop.Source: §8.1 · p. 34
  • Separating planning from execution semantics supports localized replanning and lets practitioners select PDDL-based planners without compatibility constraints or monolithic-planning explosion.The discussion attributes BT-based replanning difficulties to their conflation of task ordering and success criteria, which APTree represents separately.Source: §8.1 · pp. 34–35
  • Coordinating multiple symbolic planners within one execution model improves planning modularity and scalability through hierarchical and horizontal decomposition.Per-invocation planning latency remained stable; faster planners reduced latency without loss of plan quality.Source: §8.1 · p. 35

8.2. Application Scope, Limitations and Future Work

  • Only one prefabrication category is evaluated; applying APTree elsewhere requires domain-specific action, object, and predicate types, and may require new execution policies.Empirical validation of domain transfer remains future work.Source: §8.2 · p. 35
  • Case-study setup required substantial planner selection and PDDL-domain development, while problem subdivision, execution coordination, and planner assignment also require manual configuration.Domain files may be reused for similar problems; automation of these configuration steps remains future work.Source: §8.2 · pp. 35–36
  • The evaluation does not thoroughly assess runtime performance, and progress guarantees for adversarial overlapping partial orders remain unestablished and unevaluated.Execution-level metrics require real or simulated robotic deployment with real-time planning and environmental feedback.Source: §8.2 · pp. 35–36

9. Conclusion

APTree applies symbolic planners repeatedly through a DSL shared by planning and execution, and uses execution models in planning. In the full-scale prefabrication case study, it detected injected errors, scaled beyond monolithic planning, and produced plans matching the expert reference; formal safety results depend on stated assumptions.

9. Conclusion

  • In the full-scale prefabrication case study, APTree detected all injected typing and logical errors missed by the baseline, scaled beyond monolithic planning through automatic decomposition, and matched the expert reference plan.Formal analysis guarantees safety of composed execution and local replanning only under assumptions including planner soundness, non-interference, and atomic mid-level execution.Source: §9 · p. 36
  • APTree repeatedly applies symbolic planners through a DSL shared by planning and execution, using execution models as part of planning.Source: §9 · p. 36
  • The paper presents APTree as a bridge between AI task planning and construction robotic fabrication.Source: §9 · p. 36

Declaration of Generative AI and AI-assisted Technologies in the Writing Process

The authors report using Copilot, Gemini, and ChatGPT to proofread and edit the text, and Cursor AI to assist with implementation. They reviewed and edited the resulting content and take responsibility for the publication.

Declaration of Generative AI and AI-assisted Technologies in the Writing Process

Appendix A. Additional Material

The appendix supplies models referenced in Section 7, including intentionally invalid APTree and BT.CPP models for evaluating design-time error detection. The injected cases cover configuration, modeling, typing, and syntax issues; runtime-only logical errors are not represented in the models.

Appendix A. Additional Material

  • The appendix's intentionally invalid APTree and BT.CPP models support design-time error-detection evaluation; runtime-only logical errors are not represented.Errors marked NA or PD for a framework are also omitted from its corresponding model.Source: Appendix A · pp. 40–41
  • Injected cases include a missing planner configuration or domain, and using FF with a domain containing unsupported PDDL 2.1 language.Source: Appendix A · p. 40
  • Other cases test invalid BT action structure, a mismatch between the execution-model action sequence and symbolic plan, and references to undefined objects or types.The examples include an action node with children, a nonexistent lower plate, and an undefined Rail type.Source: Appendix A · pp. 40–41
  • The models also inject undefined action types and parameter-count or parameter-type mismatches between actions and generated plans.Source: Appendix A · p. 41
  • Syntax and structural cases include missing braces or closing tags, swapped root and behavior-tree keywords, and missing required keywords.Swapping the keywords also triggers an unexpected-token error.Source: Appendix A · p. 41

Appendix B. Formal Correctness Analysis

The appendix presents formal proofs and invariants for plan correctness and composability under dynamic node insertion, replanning, and partially ordered interleaved execution. Its setup distinguishes high-level planning domains from mid-level domains used for refined or replanned subtrees and defines symbolic planners as returning a plan or failure.

Appendix B. Formal Correctness Analysis

  • The analysis establishes plan correctness and composability under dynamic node insertion, replanning, and partially ordered interleaved execution.Source: Appendix B · p. 42
  • High-level domains support high-level planning, while mid-level domains refine them into finer-grained actions and fluents for decomposition or replanning.Mid-level problems are instantiated lazily from the world state at refinement or replanning time.Source: Appendix B · p. 42
  • The analysis assumes the All success criterion; its results do not apply to partial-success criteria where a dynamic flow node can report success without its planning goal holding.Source: Appendix B · p. 42
  • A symbolic planner returns a finite action sequence for a planning problem or reports failure if no plan is found.Source: Appendix B · p. 43
  • Goal interference occurs when two goals require opposite truth values for a fluent, or a plan's action effects contradict a goal literal.Source: Appendix B · p. 43

Appendix C. Replicability and Data Availability

The paper archives the artifacts needed to reproduce its listings, tables, and results, including DSL models, execution logs, and formal verification materials.

Appendix C. Replicability and Data Availability

  • The DaRUS repository permanently archives artifacts for reproducing the paper’s listings, tables, and results, with configurations v1.0 without replanning and v2.0 with replanning.A development version is also maintained on GitHub.Source: Appendix C · p. 46
  • The archived artifact is organized into APTreeDSL, APTreeExecutionEngine, and Lean components.Source: Appendix C · p. 46
  • The DSL archive includes grammars, functions, example behavior trees, livMatS input and generated models, intentionally invalid models, and PlanSys2 comparison tests.Source: Appendix C · p. 46
  • The execution archive provides source code, an entry point, generated logs and summaries, and the logs used in the paper.Source: Appendix C · p. 46
  • The Lean directory contains the machine-checked Lean 4 formalization and proof-reproduction instructions.Source: Appendix C · p. 46

Related papers

Loading 2610.18523v1…