Optimal Scene Graph Planning with Large Language Model Guidance

Advances in robot perception and computer vision have enabled metric-semantic mapping [1, 2, 3, 4, 5, 6, 7, 8, 9], offering rich information in support of robot autonomy. Beyond single-level maps, hierarchical models encode topological relations among local maps and semantic elements [10, 11]. A scene graph [11] is a prominent example that models buildings, floors, rooms, objects, and occupancy in a unified hierarchical representation. Scene graph construction can be done from streaming sensor data [12, 5, 13]. The metric, semantic, and topological elements of such models offer the building blocks for robots to execute semantic tasks [14]. The objective of this work is to approach this challenge by generalizing goal-directed motion planning in flat geometric maps to natural language task planning in scene graphs.

Connecting the concepts in a natural language task to the real-world objects they refer to is a challenging problem, known as symbol grounding [15]. Large language models (LLMs), such as GPT-3 [16], BERT [17], and LLaMA [18], offer a possible resolution with their ability to relate entities in an environment model to concepts in natural language. Chen et al. [19, 20] use LLMs for scene graph labeling, showing their capability of high-level understanding of indoor scenes. Shah et al. [21] use GPT-3 to parse text instructions to landmarks and the contrastive language image pre-training (CLIP) model [22] to infer a joint landmark-image distribution for visual navigation. Seminal papers [23, 24] in the early 2000s established formal logics and automata as powerful representations of robot tasks. In work closely related to ours, Chen et al. [25] show that natural language tasks in 2D maps encoded as sets of landmarks can be converted to signal temporal logic (STL) [26] via LLM re-prompting and automatic syntax correction, enabling the use of existing temporal logic planners [27, 28, 29, 30, 31]. Beyond temporal logics, other expressive robot task representations include the planning domain definition language [32], Petri nets [33, 34], and process algebra [35]. However, few of the existing works have considered task specification in hierarchical models. We use an LLM to translate a natural language task defined by the attributes of a scene graph to a linear temporal logic (LTL) formula. We describe the scene graph to the LLM via an attribute hierarchy and perform co-safe syntax checking to ensure generation of correct and finite-path verifiable LTL. Further, we develop an approach to obtain task execution guidance from the LLM, which is used to accelerate the downstream task planning algorithm.

Given a symbolically grounded task representation, the next challenge is to plan its execution in a hierarchical model efficiently. A key component for achieving efficiency in traditional goal-oriented planning in single-level environments is the use of guidance from a heuristic function. Heuristics play a critical role in accelerating both search-based [38, 39] and sampling-based [40, 41] planners. More complex tasks than goal reaching involve sequencing, branching, and recurrence, making heuristic guidance even more important for efficiency. Our work is inspired by Fu et al. [29] who develop an admissible heuristic for LTL planning in probabilistic landmark maps. We extend the approach by (a) generalizing to hierarchical scene graphs via multi-resolution planning, (b) designing a consistent LTL heuristic allowing acceleration over admissible-only heuristic planning, and (c) introducing an LLM heuristic allowing acceleration from LLM semantic guidance while retaining optimality guarantees via multi-heuristic planning. Our approach is enabled by the anytime multi-resolution multi-heuristic A* (AMRA*) [37], which combines the advantages of multi-resolution A* [42] and multi-heuristic A* [39]. Our key contribution is to define the nodes, edges, and costs of a hierarchical planning domain from a scene graph and to introduce guidance from a consistent LTL heuristic and a semantically informed LLM heuristic.

Related works consider object search and semantic goal navigation in unknown environments, represented as semantic occupancy maps [43], topological maps [44], or scene graphs [45, 46]. Shah et al. [43] develop an exploration approach that uses an LLM to score subgoal candidates and provide an exploration heuristic. Kostavelis et al. [44] perform place recognition using spatial and temporal proximity to obtain a topological map and encode the connectivity of its attributes in a navigation graph to enable Dijkstra planning to semantically specified goals. Amiri et al. [45] employ a scene graph generation network to construct a scene graph from images and a partially observable Markov decision process to obtain an object-search policy. Ravichandran et al. [46] embed partial scene graph observations in feature space using a graph neural network (GNN) and train value and policy GNNs via proximal policy optimization. In contrast with these works, we consider significantly more general missions but perform planning in a known scene graph.

In summary, this paper makes the following contributions.

• •

  We use an LLM to translate natural language to LTL tasks over the attributes of a scene graph.

• •

  We construct a hierarchical planning domain capturing the structure of the scene graph and LTL task.

• •

  We design new LTL and LLM heuristic functions for planning, and prove that the LTL heuristic is consistent.

• •

  We employ hierarchical multi-heuristic planning to guarantee efficiency (due to LLM semantic guidance) and optimality (due to LTL consistent guidance), despite potential inadmissibility of the LLM heuristic.

Consider an agent planning a navigation mission specified in terms of semantic concepts, such as objects and regions, in a known environment. We assume that the environment is represented as a scene graph [11].

A scene graph provides a hierarchical semantic description of an environment, such as a building, in terms of floors, rooms, objects, and occupancy (see Fig. 1). For example, the graph nodes $\mathcal{V}$ may represent free space, while the objects may be encoded as an attribute set $\mathcal{A}_{1}$ such that an object $o\in\mathcal{A}_{1}$ is associated with a free region $\mathcal{V}_{o}\subset\mathcal{V}$ around it. Similarly, rooms may be represented as a set $\mathcal{A}_{2}$ such that a room $r\in\mathcal{A}_{2}$ is associated with a free-space region $\mathcal{V}_{r}\subset\mathcal{V}$.

Given the initial agent location $s\in\mathcal{V}$, and a cost function $c:\mathcal{E}\mapsto\mathbb{R}_{>0}$, our objective is to plan a sequence of scene graph nodes (path) that achieves a mission $\mu$ with minimal cost. We assume $\mu$ is provided in natural language using terms from the attribute sets $\mathcal{A}_{k}$ of the scene graph. An example scene graph mission is provided in Fig. 1.

To interpret a natural language mission, we define atomic propositions whose combinations can capture the mission requirements. An atomic proposition $p_{a}:\mathcal{V}\mapsto\{\mathsf{false},\mathsf{true}\}$ associated with attribute $a\in\mathcal{A}_{k}$ of the scene graph $\mathcal{G}$ evaluates true at node $s\in\mathcal{V}$ if $s$ belongs to the nodes $\mathcal{V}_{a}$ that satisfy attribute $a$. We denote this by $p_{a}(s):s\in\mathcal{V}_{a}$. The set of all atomic propositions at $s\in\mathcal{V}$ is denoted by:

Intuitively, $p_{a}(s)$ being $\mathsf{true}$ means that the agent is at node $s$ that satisfies attribute $a$, e.g., reaching an object in $\mathcal{A}_{1}$ or being in a room in $\mathcal{A}_{2}$. Avoiding an object or leaving a room can be specified via the negation of such propositions. To determine which atomic propositions are satisfied at a particular node, we define a labeling function.

The labels along a path $s_{1:T}$ are obtained as $\ell(s_{1:T})=\ell(s_{1})\ell(s_{2})\ldots\ell(s_{T})$ and are called a word. A word contains information about the objects, rooms, and floors that an agent visits along its path in a scene graph. We can decide whether the agent path satisfies a mission $\mu$ by interpreting its word. We denote a word $\ell(s_{1:T})$ that satisfies a mission $\mu$ by $\ell(s_{1:T})\models\mu$, and define the precise semantics of this notation in Sec. III. With this, we are ready to state the problem of natural language mission planning in scene graphs.

We use an LLM to translate natural language missions to logic formulas over the scene graph propositions $\mathcal{A}\!\mathcal{P}$. The key challenge is to describe the structure of a scene graph $\mathcal{G}$ to an LLM and ask it to translate a mission $\mu$ to a logic formula $\phi_{\mu}$. We focus on linear temporal logic (LTL) [47] with syntax in Table. I due to its popularity and sufficient expressiveness to capture temporal ordering of propositions.

We require a syntactically co-safe formula [48] to allow checking its satisfaction over finite agent paths. A co-safe LTL formula can be satisfied by a word $\ell(s_{1:T})$ that consists of a finite prefix followed by a (potentially infinite) continuation that does not affect the formula’s truth value. LTL formulas that contain only $\mathbf{X}$ and $\mathbf{U}$ temporal operators when written in negated normal form ($\neg$ appears only in front of atomic propositions) are syntactically co-safe [48].

To use an LLM for scene understanding, it is necessary to design a prompt that describes the scene graph $\mathcal{G}$ succinctly. Otherwise, the input might exceed the model token limit or confuse the model about the relationship between the sentences. For this aim, we simplify the scene graph $\mathcal{G}$ into an attribute hierarchy $\bar{\mathcal{G}}$ that compactly represents scene entities in a YAML format. In our setup, the top level of $\bar{\mathcal{G}}$ contains floors $f\in\mathcal{A}_{3}$. The rooms $r_{f}$ on floor $f$ are defined as $\left\{r\in\mathcal{A}_{2}|\mathcal{V}_{r}\subseteq\mathcal{V}_{f}\right\}$, and nested as children of floor $f$. Additionally, each room $r$ stores connections to other rooms on the same floor. Similarly, the objects in room $r$, $\left\{o\in\mathcal{A}_{1}|\mathcal{V}_{o}\subseteq\mathcal{V}_{r}\right\}$, are stored as children of room $r$. Each entity in $\bar{\mathcal{G}}$ is tagged with a unique ID to differentiate rooms and objects with the same name. See Fig. 2a for an example attribute hierarchy. In our examples, we define attributes for floors, rooms, and objects and the attribute hierarchy contains $3$ levels but this can be extended to more generalized attribute sets (e.g., level for object affordances). The attribute hierarchy removes the dense node and edge descriptions in $\mathcal{G}$ which are redundant for mission translation, leading to a significant reduction in prompt size.

Given the natural language mission $\mu$ and the attribute hierarchy $\bar{\mathcal{G}}$, the first call to the LLM is only responsible to extract unique IDs from the context of $\mu$, outputting $\mu_{\text{unique}}$. This step facilitates LTL translations by separating high-level scene understanding from accurate LTL generation. Specifically, this step links contextually rich specifications, which can be potentially difficult to be parsed, to unequivocal mission descriptions that are void of confusion for the LLM when it comes to LTL translation (Fig. 2b). The list of entities involved in the mission are extracted from $\mu_{\text{unique}}$ using regular expression, and stored as $\mu_{\text{regex}}$. This allows to inform the LLM about the essential parts of the mission $\mu_{\text{unique}}$, without providing $\bar{\mathcal{G}}$. The savings in prompt size are used to augment the prompt with natural language to LTL translation examples expressed in pre-fix notation. For instance, $\phi\wedge\varphi$ is expressed as $\wedge\phi\varphi$ in pre-fix format. This circumvents the issue of balancing parenthesis over formula $\phi_{\mu}$. Ultimately, the LTL translation prompt includes $\mu_{\text{unique}}$, $\mu_{\text{regex}}$, and the translation examples (Fig. 2c).

The translated LTL formula $\phi_{\mu}$ is verified for syntactic correctness and co-safety using an LTL syntax checker. Further calls of the LLM are made to correct $\phi_{\mu}$ if it does not pass the checks, up to a maximum number of allowed verification steps, after which human feedback is used to rephrase the natural language specification $\mu$ (Fig. 2d). Once the mission $\mu$ is successfully translated into a co-safe LTL formula $\phi_{\mu}$, we can evaluate whether an agent path $s_{1:T}$ and its corresponding word $\ell(s_{1:T})$ satisfy $\phi_{\mu}$ by constructing an automaton representation of $\phi_{\mu}$ (Fig. 2e).

A co-safe LTL formula $\phi$ can be translated into a deterministic automaton $\mathcal{M}_{\phi_{\mu}}$ using model checking tools such as PRISM [49, 50] or Spot [51]. The automaton checks whether a word satisfies $\phi_{\mu}$. A word $\ell_{1:T}$ is accepted by $\mathcal{M}_{\phi_{\mu}}$, i.e., $\ell_{1:T}\models\phi_{\mu}$, if and only if the state $q_{T+1}$ obtained after transitions $q_{t+1}=T(q_{t},\ell_{t})$ for $t=1,\ldots,T$ is contained in the final states $\mathcal{F}$. Hence, a path $s_{1:T}$ satisfies a co-safe LTL formula $\phi_{\mu}$ if and only if its word $\ell(s_{1:T})$ contains a prefix $\ell(s_{1:t})$ that is accepted by $\mathcal{M}_{\phi_{\mu}}$.

We use the structure of the scene graph $\mathcal{G}$ with guidance from the automaton $\mathcal{M}_{\phi_{\mu}}$ and the LLM’s mission semantics understanding to achieve efficient and optimal planning.

To evaluate our method, we use Allensville (1-floor), Benevolence (3-floor) and Collierville (3-floor) from the 3D Scene Graph dataset [11]. For each scene, we designed 5 missions (some are shown in Table II). For each mission, we used 5 initial positions across different floors and rooms.

We use GPT-4 [53] to translate missions to LTL formulas, and Spot [51] for LTL formulas to automata as described in Sec. III. Following Sec. IV-D, we use GPT-4 [53] to generate the LLM heuristic function $h_{\textsc{LLM}}$. Given a scene graph $\mathcal{G}$, the mission described by the automaton $\mathcal{M}_{\phi}$, the LTL heuristic $h_{\textsc{LTL}}$, and the LLM heuristic $h_{\textsc{LLM}}$, we construct the hierarchical planning domain and run AMRA*.

Fig. 6 shows a path in Benevolence for the mission in Table II. Starting from the empty room on floor 0, the agent goes to the bathroom entrance without approaching the sink, and then proceeds upstairs to floor 1, finally reaching a chair in the dining room without entering the living room.

Since planning domains with different hierarchy levels and different heuristics per level can be constructed, we compare different setups to investigate the benefit of using our LLM heuristic. With all hierarchy levels having an LTL heuristic, we design 7 setups: occupancy level only without LLM heuristic (A*), all levels available but without LLM heuristics (NO-LLM), all levels with LLM heuristics (ALL), and one of the levels with LLM heuristic (OCC, OBJ, ROOM, FLR). Fig. 8 shows that the ALL setup manages to return a feasible path much faster than others thanks to the LLM guidance across all hierarchical levels, while it also approaches the optimal solution within similar time spans.

As an anytime algorithm, AMRA* starts searching with large weight on the heuristics, then reuses the results with smaller heuristic weights. As the planning iterations increase, the path gets improved. When the heuristic weight decays to 1, we obtain an optimal path. To further investigate the benefits of using LLM heuristics, we compare the number of node expansions per planning iteration. As shown in Fig. 8, applying our LLM heuristic to any hierarchy level reduces the node expansions significantly, which indicates that our LLM heuristic produces insightful guidance to accelerate AMRA*. An exciting observation is that the more hierarchy levels we use our LLM heuristic in, the more efficient the algorithm is. This encourages future research to exploit scene semantic information further to accelerate planning.

AMRA* allows a robot to start executing the first feasible path, while the path optimization proceeds in the background. Tables IV and IV shows the time required to compute the first path, the path cost relative to the optimal path, and the time required to find an optimal path. The ALL configuration outperforms other setups in speed of finding the first path and the optimal path when the scene gets more complicated.

We demonstrated that an LLM can provide symbolic grounding, LTL translation, and semantic guidance from natural language missions in scene graphs. This information allowed us to construct a hierarchical planning domain and achieve efficient planning with LLM heuristic guidance. We managed to ensure optimality via multi-heuristic planning, including a consistent LTL heuristic. Our experiments show that the LLM guidance is useful at all levels of the hierarchy for accelerating feasible path generation.