Integrating Intent Understanding and Optimal Behavior Planning for
Behavior Tree Generation from Human Instructions

We deliberately design LLM prompts to provide context for goal generation, similar to Singh et al. (2022); Ahn et al. (2022). Our prompts consist of four components: (1) Objects. The set of available objects. To better define the domains of predicates, we categorize objects into several classes, such as $<$food$>$ and <place>. (2) Condition Predicates. The set of condition predicates. The domain of a predicate is indicated by category, such as RobotNear$($<place>$)$ and On$($<food>,<place>$)$. (3) Few-shot Demonstrations. A few instruction-goal pairs as examples to teach the LLM on goal interpretation. The number of demonstrations does not need to be large, but it is beneficial to showcase as much diversity in both grammar and user’s intention as possible. (4) System. An explanatory text provides context and the prompt for instructing the LLM to produce a goal in the correct format. We found that few-shot demonstrations have a significant impact on the LLM’s ability to interpret goals, as language models have been shown to be few-shot learners Brown et al. (2020). We conducted ablation experiments in Section 4.2 to analyze its impact.

We introduce automatic reflective feedback to further enhance grammar accuracy, drawing inspiration from Liu et al. (2023b). When the LLM produces an output, the syntax checker evaluates whether the output forms a WFF, while the semantic checker further verifies the validity of predicates and objects. If errors are detected, we re-input the instruction to the LLM with additional prompt to correct these errors. While we initially provide whitelists of objects and condition predicates in the original prompt, we augment the prompt with blacklists and additional context to instruct the LLM not to include the blacklisted texts in the output again. If errors persist, we continue to apply reflective feedback, gradually expanding the blacklists, until all grammar errors are corrected, or the maximum retry limit is reached.

A grammatically correct goal will ultimately undergo normalization into Disjunctive Normal Form (DNF). This normalization offers two significant advantages. Firstly, it effectively eliminates ambiguity from WFFs, which is crucial when assessing the equivalence of two goals, particularly in evaluating the semantic correctness of the model’s outputs on the evaluation dataset. Secondly, each conjunction within DNF can be regarded as a sub-goal. When the robot accomplishes any one of these sub-goals, it is considered a success, as these sub-goals are represented as disjunctive relations. This enables us to design a modular algorithm for optimal behavior planning.

We continuously pop the condition $c\in\mathcal{C}_{U}$ with the minimum cost (line 8). This process aims to explore the condition space following the shortest path from $g_{i}$. For each popped condition $c$, we explore its neighboring conditions by iterating through all available actions (line 9) and identifying those that can reach the condition $c$ after execution. The neighboring conditions are generated similarly to the process in the BT Expansion Cai et al. (2021) (lines 10-11), and can be denoted as: $c_{a}\leftarrow pre(a)\cup c\setminus add(a)$. Then we disregard $c_{a}$ in the following two cases (line 12): (1) $c_{a}\in\mathcal{C}_{E}$, indicating that it has already been expanded and its shortest path is found. (2) $D(c)+D(a)\geq D(c_{a})$, showing that $c_{a}$ has been explored and the path cost found is equal or lower. In both cases, further exploration or updates of $c_{a}$ are unnecessary. If neither case applies, we explore $c_{a}$ by updating $D(c_{a})$, adding $c_{a}$ to $\mathcal{C}_{U},$ and recording the subtree $Sequence(c_{a},a)$ leading to $c_{a}$ (line 13-15). After exploring all the neighbors of $c$, it is removed from $\mathcal{C}_{U}$ (line 16).

After exploring $c$, we integrate it into the current BT $\mathcal{T}$. This involves adding the subtree $\mathcal{M}(c)$ as a child node of the root fallback node (line 18). The algorithm continues to explore the condition space until it expands a condition $c$ that holds in the initial state $s_{0}$ (line 19). At this point, we record the total cost of the subtree for $g_{i}$ as $D(\mathcal{T})=D(c)$ (line 20), and the exploration-expansion loop is immediately terminated (line 21). If $s_{0}$ is not reached, we add $c$ to the expanded set $\mathcal{C}_{E}$ (line 22). It is important to note that this method of expansion might include conditions that are not part of the shortest path. However, this does not affect the optimality since these extra conditions will not be visited along the shortest path. This approach enhances the BT’s reactivity and robustness when the state deviates from the original path, ensuring that the path starting from each expanded condition is optimal.

For an expanded optimal subtree, we propose a simple but efficient method to compact its structure and improve runtime efficiency. During compaction, we recursively extract common literals from two adjacent conditions to create smaller conditions for checking. Consider a BT produced through the exploration and expansion process. If two adjacent subtrees have conditions $c_{1}$ and $c_{3}$, respectively (as illustrated in Fig. 2), both conditions need to be checked during runtime. After compaction, if $c_{1}\cap c_{3}\neq\emptyset$, a new condition $c^{\prime}=c_{1}\cap c_{3}$ will be created and checked first during ticking. If it does not hold, the conditions $c_{1}\setminus c_{3}$ and $c_{3}\setminus c_{1}$ will be skipped, thereby saving time. The compacted subtrees can recursively join the compaction with its neighbors due to the modularity of BT. We evaluated the impact of the maximum recursion depth during compaction on condition check count in Section 4.3.

Once all subtrees have been generated, we can assemble the final optimal BT. We start by sorting all the subtrees in ascending order according to their total costs (line 24). This ensures that the BT will prioritize the feasible paths with the lowest cost. Then, we construct the final BT $\mathcal{T}_{*}$ by adding the sorted subtrees under a fallback node (line 25). After this, the algorithm ends and returns $\mathcal{T}_{*}$ as the optimal BT to achieve the final goal $G$ at minimal cost.

To conduct the ablation analysis on the number of demonstrations, we reduced the number of demonstrations while keeping the objects, predicates, and system explanations constant. It is observed that when no demonstrations are provided (zero-shot), both GA and IA significantly decrease across three levels of difficulty. Furthermore, IA is particularly lower than GA in the zero-shot setting, which again confirms the challenge for LLM to learn intent understanding rather than learning logical grammar only in explanatory prompts. Without any demonstrations, the pre-trained LLM struggles to provide WFF-represented goals that align with the user’s intent. However, there is a notable improvement in performance after adding just one demonstration (one-shot). This phenomenon indicates that one example can be more effective than a lengthy explanation. The results underscore the importance of including examples in prompts and also highlight the LLM’s few-shot learning ability in interpreting goals.

We then performed the ablation analysis on the maximum retry times with reflective feedback. The results show that without feedback (GA-NF), the performance is markedly decreased, especially in the absence of demonstrations. Similarly to the number of demonstrations, GA improved when the LLM is allowed to retry only once (GA-1F), and an increase in the number of feedback times continuously improved grammar correctness. These results confirm the effectiveness of reflective feedback.

In addition to the dataset in the café scenario, we also designed random test sets to verify the generality of OBTEA. Inspired by Cai et al. (2021), we randomly generate various optimal behavior planning tasks by creating action sequence paths from the initial state to the goal and then randomly adding other actions. In contrast to previous work, our datasets are represented using first-order logic. The problem scale is mainly determined by the number of objects ($\mathcal{O}$), condition predicates ($\mathcal{P}_{c}$), and action predicates ($\mathcal{P}_{a}$). To increase the number of valid paths to the goal, we can randomly copy the actions in the original path several times, but assign different costs, denoted as maximum action copies (MAC). Further details can be found in the appendix.

Table 3 shows the results averaged over 1000 runs. The results again emphasize OBTEA’s proficiency in achieving lower action costs and condition node ticks across all cases with varying complexity. In particular, in the most complex case 9, OBTEA significantly reduces costs by more than $50\%$, and condition node ticks decrease by approximately $30\%$. When there are more available paths to reach the goal, the costs of BTs found by OBTEA are smaller than the baseline. Note that while OBTEA has achieved improvements, its additional time overhead is also acceptable. The test results and discussions regarding planning time are in the appendix.

We then performed an ablation analysis on the impact of the maximum recursion depth during compaction. Table 3 shows that when we remove compaction (OBTEA-NC), the condition node ticks increase significantly in all cases. Experiments in café scenarios (Figure 3) show that condition node ticks decrease rapidly as the recursion depth increases when the recursion depth is small and then become rather constant when we continuously increase the depth. This means that the recursion depth does not need to be set too large to achieve optimal performance in the café scenario.