Backward chained behavior trees with deliberation for multi-goal tasks

Backward chained behavior trees (BTs) are an approach to generate BTs through backward chaining. Starting from the goal conditions for a task, this approach recursively expands unmet conditions with actions, aiming to achieve those conditions. It provides disturbance rejection for robots at the task level in the sense that if a disturbance changes the state of a condition, this condition will be expanded with new actions in the same way. However, backward chained BTs fail to handle disturbances optimally in multi-goal tasks. In this paper, we address this by formulating it as a global optimization problem and propose an approach termed BCBT-D, which endows backward chained BTs with the ability to achieve globally optimal disturbance rejection. Firstly, we define Implicit Constraint Conditions (ICCs) as the subsequent goals of nodes in BTs. In BCBT-D, ICCs act as global constraints on actions to optimize their execution and as global heuristics for selecting optimal actions that can achieve unmet conditions. We design various multi-goal tasks with time limits and disturbances for comparison. The experimental results demonstrate that our approach ensures the convergence of backward chained BTs and exhibits superior robustness compared to existing approaches.