Improving Efficiency of Answer Set Planning with Rough Solutions from Large Language Models for Robotic Task Planning

1 Introduction

Answer Set Programming (ASP) [Lifschitz, 2019] has been applied to robotic task planning [Chen et al., 2013; Tran et al., 2023]. However, answer set planning still faces challenges in real-world applications due to the extensive domain knowledge required and the limited computational efficiency in large-scale problems.

Conversely, Large Language Models (LLMs), such as GPT4 [OpenAI, 2023] and Llama 3 [Meta AI, 2024], possessing broad foundational knowledge, are well-suited for task planning in open-world scenarios [Kambhampati et al., 2024]. It is hard for LLMs to directly generate executable plans that follow specific constraints of the robot [Wu et al., 2023]. For instance, an LLM-generated plan might skip essential actions like "plugin washing machine" before "switch on washing machine". However, these LLM-generated rough solutions serve as valuable guidance.

∗Corresponding author

In this paper, we consider how to utilize these rough solutions to speed up answer set planning. Rough solutions from LLMs can improve the computational efficiency of answer set planning in two different ways. Firstly, inspired by the TLPLAN system [Bacchus and Kabanza, 2000] that utilizes domain-specific control knowledge to speed up the planning process, we encode the ASP program to refine the rough plan to accomplish the task. In this sense, we define the planning problem with a rough solution and provide an ASP encoding to generate executable plans for the problem. Secondly, we consider how to reduce the domains of variables to speed up the grounding process in ASP. However, the ground ASP program obtained by a reduction may generate different results from the original program. To address this, we introduce the notions of admissible reduction and safe reduction that preserve possible solutions for the original program, while admissible reductions are more helpful for answer set planning. It is hard to identify admissible or safe reductions. Then we propose a sufficient condition with the notions of loops and loop formulas [Lin and Zhao, 2004] for identifying admissible reductions and apply the condition in our encoding for answer set planning.

For a typical task planning problem with hundreds of objects and requiring dozens of actions to accomplish the task, the above methods can reduce the computing time from more than 2 hours to less than 5 seconds. Building on the two speedup methods, we introduce CLMASP (see Figure 1), an approach that couples LLMs with ASP for robotic task planning. Our contributions are as follows:

• We consider leveraging rough solutions from LLMs to accelerate answer set planning. To enhance ASP planning efficiency, we propose two methods: (1) defining the planning problem using a rough solution refined by an ASP program, and (2) introducing admissible and safe reductions, along with a sufficient condition based on loops and loop formulas to reduce variable domains.
• We provide a framework, CLMASP, that leverages the accelerated ASP planning methods to improve both computational efficiency and the executability of plans, as demonstrated through experiments on the VirtualHome platform.

2 RelatedWork

2.1 Improve Efficiency of ASP

Reducing domains of variables to reduce the size of ground programs has not been considered much in ASP. Lazy grounding [Dal Palu et al., 2009] requires a new ASP solver implementation, rather than using existing solvers such as clingo [Gebser et al., 2019]. Although methods such as rewriting [Pearce, 2004; Ji et al., 2015a; Ji et al., 2016], splitting [Lifschitz and Turner, 1994; Ji et al., 2015b; Fandinno and Lierler, 2023], and forgetting [Ji et al., 2015c; Saribatur and Woltran, 2024] have been extensively explored, they often require some sense of equivalence during the simplification of logic programs. Abstraction [Saribatur and Eiter, 2021; Saribatur et al., 2021] approximates answer sets without losing any, by simplifying logic programs so that every answer set of the original program corresponds to one in the abstract program. However, it does not explicitly consider the grounding process. In contrast, our admissible and safe reductions operate at the grounding level by pruning constants to reduce ground program size while preserving relevant answer sets. To our knowledge, such reductions have not been explored in ASP.

2.2 LLMs in Robotic Task Planning

Recent research has explored the application of LLMs in robotic task planning using prompt-based methods that integrate domain knowledge through natural language [Huang et al., 2022; Song et al., 2023] or pseudo-Python code [Singh et al., 2023; Liang et al., 2023]. However, LLMs often struggle to retain crucial information in long-horizon tasks. To address these limitations, the integration of external tools like knowledge base feedback [Gou et al., 2023], local checkers [Chen et al., 2024], and physical environment interactions [Bhat et al., 2024] has been proposed, alongside fine-tuning LLMs for specific tasks to minimize inaccuracies [Xiang et al., 2024; Mu et al., 2024]. Nevertheless, robotic task plans still struggle to fully conform to action models and environmental constraints, complicating the successful completion of tasks.

In contrast, a well-designed symbolic planner can yield comprehensive and interpretable results within a specific domain [Pan et al., 2023]. Current research is exploring the integration of symbolic planners with LLMs [Liu et al., 2023; Yang et al., 2023]. Compared to our proposed CLMASP, existing approaches primarily use LLMs for translating informal to formal representations, neglecting their planning and commonsense reasoning capabilities, and fail to adapt symbolic planners for effective collaboration with large models.

3 Preliminaries

We first recall the definition of Answer Set Programming (ASP) with variables [Van Harmelen et al., 2008], focusing on key concepts used in our method. We then review loops and loop formulas [Lin and Zhao, 2004], and finally discuss the ASP encoding for robot task planning [Tran et al., 2023].

3.1 Answer Set Programming with Variables

Consider a first-order vocabulary Θ = (P, D), where P and D are finite, non-empty sets of predicates and constants, respectively. A term is a constant from D or a variable from a set of variables V. An atom has the form p(t1, . . . , tn) where p ∈ P and each ti is a term. A ground atom contains no variables. An ASP program Π with variables consists of rules of

where Ai are atoms (0 ≤ i ≤ n) and n ≥ 1. Each rule r is also written as head(r) ← body(r), where body(r) = A1 ∧ · · ·∧Am∧¬Am+1 ∧· · ·∧¬An, body+(r) = {A1, . . . , Am} and body-(r) = {Am+1, . . . ,An}. Π is ground if all its rules are ground; Π is safe if each variable in rule r appears in body+(r). Safety is achieved using domain predicates - unary predicates given as facts, universally true for all constants used to ground the variables. The Herbrand universe of Π, denoted by HU(Π), consists of the set of all constants, that is, HU(Π) = D.

A complete variable assignment σ maps each variable in V to a constant in D. For a rule r, the ground rule rσ replaces every variable in r with its value in σ. The set of all ground instances of r over D, denoted r|D, includes all possible ground rules with constants from D:

For an ASP program Π, we can construct its ground program Π|HU(Π) = ⋃r∈Π r|HU(Π), referred to as the grounding result.

Given an interpretation I, i.e., I is a set of ground atoms, I satisfies a ground rule r, if head(r) ∈ I whenever body+(r) ⊆ I and body-(r) ∩ I = ∅. An interpretation I is a model of Π, if it satisfies every ground rule in Π|HU(Π). I is a minimal model if there is no other model J of Π such that J ⊂ I.

Now, we define the answer sets of an ASP program with variables. Given an ASP program Π and an interpretation I, the Gelfond-Lifschitz reduction [Gelfond and Lifschitz, 1988] of Π on I, written ΠI , is obtained from Π|HU(Π) by deleting:

1. each rule that has not A in its body with A ∈ I, and
2. all notA in the bodies of the remaining rules.

For any interpretation I, ΠI is a ground positive ASP program, then ΠI has only one minimal model. Thus, an interpretation I is an answer set of Π iff I is the minimal model of ΠI . An ASP program may have zero, one or multiple answer sets. We focus here on normal rules; richer constructs follow in Sec. 3.3.

3.2 Loops and Loop Formulas

With the notions of loops and loop formulas, we can convert an ASP program Π into a propositional formula such that an interpretation I is an answer set of Π iff it is a model of the propositional formula. Notice that, we define the notions of loops and loop formulas on the ground ASP program Π|HU(Π), as we define the notion of answer sets on Π|HU(Π), which slightly differs from the first-order loop formulas in [Chen et al., 2006].

Given an ASP program Π, the positive dependency graph of Π, written GΠ, is a directed graph whose vertices are atoms in Π|HU(Π) and there is an arc from A to B if there is a rule r ∈ Π|HU(Π) such that A ∈ head(r) and B ∈ body+(r). A set L of ground atoms is a loop of Π if the L-induced subgraph of GΠ is strongly connected. Every singleton in Π|HU(Π) is also a loop of Π.

Given a loop L of an ASP program Π, a ground rule r ∈ Π|HU(Π) is an external support of L if head(r) ∈ L and L ∩ body+(r) = ∅. We denote R-(L,Π) to be the set of all external support rules of L in Π|HU(Π). The loop formula of L under Π, written LF(L, Π), is given by:

Theorem 1. [Lin and Zhao, 2004] Given an ASP ground program Π and an interpretation I. If I is a model of Π, then I is an answer set of Π if and only if I satisfies LF(L,Π) for all loops L of Π.

3.3 Encoding of Answer Set Planning

A robot task planning problem can be encoded as an ASP program Π [Tran et al., 2023], where each answer set I corresponds to a valid plan. Π comprises the following components:

• A set of fluents F representing states, h(f,t) (fluent f is true at time step t);
• A set of actions A represented as occurs(a,t) (action a occurs at time step t);
• Initial state s0 using fluents at time 0;
• Action preconditions as constraints on occurs(a,t);
• Effect axioms describing how actions modify fluents;
• Frame axioms for unchanged fluents;
• Goal conditions at the final time step.

Algorithm 1: ASP-based Task Planning Encoding

Input:

Πdomain: domain encoding (objects, initial states, maximum allowed timesteps (Tmax ), etc.).

Πstep: action encoding (preconditions, effects, etc.)

Πcheck : goal-checking constraints.

Output: Plan τ = ⟨s0, a1, s1, . . . , sn⟩.

• 1: Set t ← 0 {Initialize time step t to 0}
• 2: Load Πdomain, Πstep, Πcheck
• 3: while no solution found and t < Tmax do
• 4: t ← t + 1 {Increment time step t}
• 5: Ground and solve Πbase ∪Πstep(1..t) ∪Πcheck(t)
• 6: if an answer set I is found then
• 7: Extract plan τ from occurs(a, t) and h(f, t) in I
• 8: return τ
• 9: end if
• 10: end while
• 11: return "No solution found within Tmax steps."

A trajectory τ is a sequence ⟨s0, a1, s1, . . . , an, sn⟩, where each si is the state at time i (0 ≤ i ≤ n), and aj (1 ≤ j ≤ n) is the action at time j. 1 An answer set I of Π contains exactly such a trajectory, where states and actions are derived from h(f,t) and occurs(a,t) present in I respectively. A trajectory τ satisfies an encoding Π if there exists an answer set I of Π such that τ can be constructed from I.

We now describe a practical ASP encoding Π for robot task planning, using clingo's syntax [Potassco Team, 2025]. While our preceding discussion focused on normal rules, this encoding also employs constructs like choice rules. To find the shortest plan, we use clingo's incremental mode. Listing 1 shows an ASP encoding of the wash and find actions, structured per Algorithm 1. Traditional encoding includes Πdomain (Lines 3-10) defining objects, initial states, and actions; Πstep (Lines 11-22) specifying action preconditions, effects, and state transitions; and Πcheck (Lines 26-27) detailing goal constraints. When executed, the ASP solver returns an answer set "occurs(find(2),1). occurs(wash(2),2)." indicating the robot first finds object 2, then washes it.

While this encoding can scale to more complex domains by adding new rules, handling numerous constants and actions in indoor task planning can lead to inefficient planning. Section 4 explores methods to enhance computational efficiency.

4 Improve Efficiency of Answer Set Planning with Rough Solutions

Despite advances in ASP solver efficiency, real-world robot task planning remains challenging due to the computational complexity, becoming NP-complete for bounded plan lengths [Tran et al., 2023]. LLMs, with their extensive knowledge, can facilitate the planning process by generating rough solutions. This section shows how to utilize these rough solutions to speed up answer set planning by: (1) incorporat-

1 In this study, only one action is performed at each time step.

Listing 1: ASP Encoding for wash and find. Our proposed skeleton plans (Section 4.1, lines 23-25, 28) replace the traditional method (Section 3.3, commented out in lines 22, 27), both of which are compared in our experiments.

• 1 #include <incmode>.
• 2 #const tmax = 30.
• 3 #program base.
• 4 num(0..tmax). time(0) .
• 5 is (1, character ) . is (2, clothesshirt ) .
• 6 robot (1) . object (2) .
• 7 action of (wash(O)) :- object (O).
• 8 action of ( find (O)) :- object (O).
• 9 h(hand empty(1),0) . h(same loc (1,2) ,0) .
• 10 task (wash(O)) :- is (O, clothesshirt ) , object (O).
• 11 #program step( t ) .
• 12 time(T) :- num(T), T==t.
• 13 1{occurs(A,t ) : action of (A)}1.
• 14 h(clean(O), t ) :- occurs(wash(O),t) , object (O).
• 15 :- occurs(wash(O),t) , not h(hand empty(C),t-1), robot (C ), object (O).
• 16 :- occurs(wash(O),t) , not h(found(O), t-1), object (O).
• 17 h(found(O), t ) :- occurs( find (O), t ) , object (O).
• 18 :- occurs( find (O), t ) , not h(same loc(C,O), t-1), robot (C ), object (O).
• 19 h(hand empty(C),t) :- h(hand empty(C),t-1), not -h( hand empty(C),t) , robot (C).
• 20 h(same loc(C,O), t ) :- h(same loc(C,O), t-1), not -h( same loc(C,O), t ) , robot (C), object (O).
• 21 h(clean(O), t ) :- h(clean(O), t-1), not -h(clean(O), t ) , object (O).
• 22 % goal(wash(O),t):-h(clean(O), t ) , object (O).
• 23 goal( subtask(p, find (2) ,1) , t ) :- occurs( find (2) , t ) .
• 24 goal( subtask(p,wash(2) ,2) , t ) :- occurs(wash(2), t ) .
• 25 goal(p, t ) :- goal( subtask(p, find (2) ,1) ,T1), time(T1), goal( subtask(p,wash(2) ,2) ,T2), time(T2), T1<=T2, T2<=t.
• 26 #program check(t ) .
• 27 % :-query(t ) , not goal(Task, t ) , task (Task) .
• 28 :-query( t ) , not goal(p, t ) .
• 29 #show occurs /2.

ing skeleton plans into existing ASP encoding-an idea inspired by TLPLAN [Bacchus and Kabanza, 2000], which uses domain-specific control knowledge to guide the planner, and (2) reducing variable domains during grounding without losing any valid plans.

4.1 Answer Set Planning with Skeleton Plans

To enhance the efficiency of answer set planning, we introduce skeleton plans (e.g., generated by LLMs) that provide guided instructions for tasks.

A planning problem with a skeleton plan is a pair (Π, P), where Π is an ASP encoding of the planning domain, and P is a skeleton plan aligned with Π's signature. The signature comprises disjoint sets of action names (from ground terms in occurs(a,t)), fluent names (from ground atoms h(f,t)), and subtask names, with no circular subtask references. A skeleton plan P is recursively defined as:

• An action name a;
• A fluent-specification φ, formed from fluent names using propositional connectives;
• A subtask name p;
• A sequence P1; . . . ; Pm, where each Pi is a skeleton plan.

A trajectory τ = ⟨s0, a1, s1, . . . , an, sn⟩ satisfies P if:

• P = a and a = an;
• P = φ and sn satisfies φ;
• P = p and τ satisfies the skeleton plan for subtask p;
• P = P1; . . . ; Pm, and there exist 0 ≤ n1 ≤ · · · ≤ nm-1 ≤ n such that each sub-trajectory ⟨sni-1, ani-1+1, . . . , sni⟩ satisfies Pi (with n0 = 0, nm = n).

A trajectory τ is a solution to (Π, P) if it satisfies both Π and P. This implies that a plan for Π can be constructed by extending the skeleton in P into an executable plan, rather than exploring all possible action sequences, enhancing efficiency.

For example, a skeleton plan for task "wash object 2" can be:

This plan encodes a high-level instruction that the robot should first finds object 2, then washes it. Although execution details are abstracted away, it still constrains the search space and is embedded into ASP via auxiliary rules.

Skeleton plans are incorporated by adding ASP rules for subtask definitions and plan satisfaction constraints, as shown in Listing 1 (Lines 23-25, 28). This enables efficient plan refinement guided by P , compared to unconstrained planning.

Property 1. Given an encoding of the answer set planning problem Π and a skeleton plan P , a solution τ of (Π, P) always contains a plan for Π and can be computed from the answer set of the encoding of Π appending with the encoding for the skeleton plan P .

This holds because P constrains the solution space of Π without changing its underlying planning logic. Any answer set satisfying both still represents a valid plan for Π.

Property 1 enables skeleton plans to significantly reduce the search space, enhancing planning efficiency by decreasing the complexity from O((S × A)N ) to O(m × (S × A)N/m), where S is the state space size, A is the action space size, N is the maximum number of timesteps, and m is the number of skeleton steps. In our VirtualHome experiments, which involve numerous objects and relations, appropriate skeleton plans can accelerate answer set planning.

4.2 Reduce Domains of Variables

ASP solvers must ground program Π into Π|HU(Π) before computing answer sets. However, the size of Π|HU(Π) can be exponentially larger than Π, creating a performance bottleneck. For example, VirtualHome task planning problems with hundreds of objects produce groundings exceeding 16MB at time 0, causing clingo to timeout after 2 hours.

Our encoding Π ensures safety through domain predicates (unary predicates given as facts). Each variable in a rule is restricted by a domain predicate in the rule's body. For instance, in rule r at Line 14 of Listing 1, variable O is restricted by predicate object.

Since most objects are irrelevant for plan generation, we can omit them during answer set planning. This section discusses how to reduce the constant set for grounding while preserving solutions. We will define admissible reductions and safe reductions, provide a sufficient condition for admissible reduction, and demonstrate its application in speeding up answer set planning.

Definition 1. Given an ASP program Π (with variables), a set D of constants with D ⊆ HU(Π) is an admissible reduction of Π, if

• for every answer set ID of the ground program Π|D, there always exists an answer set I of Π such that ID ⊆ I.

Definition 2. An admissible reduction D of Π is also a safe reduction of Π, if

• for every answer set I of Π, there always exists an answer set ID of Π|D such that ID ⊆ I.

Note that for D ⊆ HU(Π), while Π|D ⊆ Π|HU(Π), D may neither be an admissible nor a safe reduction of Π. Consider program Π′ :

where HU(Π′ ) = {a, b}, x, y are variables appearing in Π′ . With D = {a}, Π′ |D has answer set {f(a), f(b), g(a, b)}, but Π′ has none. Thus {a} is neither an admissible nor a safe reduction, while {a, b} is both.

Theorem 2. Given a subset D of HU(Π) for an ASP program Π, deciding whether D is an admissible reduction or a safe reduction of Π is coNP-hard.

Proof. We can construct an ASP problem Π from a 3-SAT problem by adding {a ← not a′ . a′ ← not a.} for each atom a, without loss of generality, for each clause ¬a∨b∨¬c adding {← a, not b, c.}, and adding {f(o1). f(o2). ← f(x), f(y), x ̸= y.}. HU(Π) = {o1, o2}, Π|HU(Π) has no answer sets, Π|{o1} has an answer set iff the 3-SAT problem is satisfiable. Then {o1} is an admissible or a safe reduction iff the 3-SAT problem is unsatisfiable.

It is hard to identify admissible and safe reductions. In the application of answer set planning, rather than finding all solutions, we prefer to find an executable plan for the task. Then we consider the applications of admissible reduction in this paper.

With the help of the notions of loops and loop formulas, we provide a sufficient condition for admissible reduction. Definition 3. Given an ASP program Π (with variables), a set D of constants with D ⊆ HU(Π) is a loop-admissible reduction of Π, if

1. for every answer set ID of Π|D, there exists an interpretation I ′ such that ID ∪ I ′ satisfies rules in Π|HU(Π) and loop formulas for every loop L′ of Π with L′ ⊆ I ′ , and
2. there does not exist a loop L of Π such that L is not a loop of Π|D and L contains a loop L′ of Π|D with R-(L′ , Π|D) ̸= ∅.

Intuitively, we require that the rules in Π|HU(Π)\Π|D and any newly introduced loop formulas can be satisfied by ID ∪ I ′ . Theorem 3. Given a subset D of HU(Π) for an ASP program Π, if D is a loop-admissible reduction of Π, then D is an admissible reduction of Π.

Proof. Let ID be an answer set of Π|D, from the definition of loop-admissible reduction, there exists the set I ′ of groud atoms such that ID ∪ I ′ is a model of Π and ID ∪ I ′ satisfies loop formulas of loops L of Π with L ⊆ ID or L ⊆ I ′ .

To prove that D is an admissible reduction of Π, we need to show that ID ∪ I ′ is an answer set of Π. By Theorem 1, it suffices to prove that ID ∪ I ′ satisfies LF(L,Π) for all loops L of Π. Consider an arbitrary loop L of Π. We analyze all possible cases:

1. Case L ̸⊆ ID ∪ I ′ : By the the loop formula definition, the formula is vacuously true when the premise ∧A∈L A is false.
2. Case L ⊆ ID: Since ID is an answer set of Π|D and for any rule r ∈ R-(L, Π|D) ⊆ R-(L, Π), ID satisfies LF (L, Π).
3. Case L ⊆ I ′ : By condition 1 of the loop-admissible reduction definition, ID ∪ I ′ satisfies LF(L, Π).
4. Case L∩ID ̸= ∅∧L∩I ′ ̸= ∅∧L ⊆ ID ∪I ′ : We prove by contradiction that this case cannot occur. Suppose such a loop L exists. Since ID is an answer set of Π|D, by Theorem 1, there must exist a loop L′ ⊆ L ∩ ID ⊆ L that is at least a singleton, such that R-(L′ ,Π|D) ̸= ∅. However, this contradicts condition 2 of the loopadmissible reduction definition.

So, for every loop L of Π, ID ∪ I ′ satisfies LF(L, Π). Given that ID ∪I ′ is also a model of Π, by Theorem 1, ID ∪I ′ is an answer set of Π.

Notice that, a loop-admissible reduction D does not imply a safe reduction, as for a loop L ⊆ ID in both Π|D and Π|HU(D), LF(L, Π|D) ⊃ LF(L, Π|HU(D)) but not vice versa.

Application to Answer Set Planning. For a planning problem with skeleton plan (Π, P), we define a loop-admissible reduction D∗ as the minimal subset of the HU(Π), that satisfies the following conditions: (1) D ⊆ D∗ , where D is the initial set of relevant elements; and (2) D∗ is closed under the binary relation R ⊆ HU(Π)×HU(Π), such that (o1, o2) ∈ R and o1 ∈ D∗ imply o2 ∈ D∗ . Formally, D∗ can be expressed as:

This expansion primarily affects binary relations (e.g., on(o1,o2), in(o1,o2), close(o1,o2)). The resulting D∗ satisfies both conditions for loop-admissible reduction because:

• Different domain predicates restrict variables in each rule of our encoding, ensuring Π|HU(Π) \ Π|D∗ and its loop formulas are satisfiable.
• The construction of D∗ ensures the second condition of Definition 3 is met for all relevant loops.

Let Π∗ be the combination of encodings for Π and P. We can compute answer sets of Π∗ |D∗ to obtain the solution of (Π, P ).

Property 2. Given the encoding Π∗ of a planning problem with a skeleton plan (Π, P ), the expanded set D∗ of constants is a loop-admissible reduction of Π∗ . A solution of (Π, P) can be obtained from the answer set of Π∗ |D∗ .

This is guaranteed by the construction of D∗ , which ensures it contains all constants relevant to the planning problem while satisfying loop-admissible reduction conditions.

In our experiments, task planning in VirtualHome involves hundreds of objects. By reducing variable domains, we focus on dozens of objects and relations, greatly reducing ground program size. With appropriate skeleton plans, clingo computation time was cut from over 2 hours to under 5 seconds.

5 Couple LLMs with Answer Set Planning

To effectively integrate LLM common sense with ASP's reasoning capabilities for real-world planning tasks, we propose CLMASP as a two-phase planning framework, as illustrated in Figure 1. This framework first leverages the LLM for rough planning and grounding, followed by ASP to elaborate the skeleton plan into a final solution.

5.1 Generating a Skeleton Plan by LLMs

Initial Plan Generation. Given a task description, primitive actions, environmental object categories, and three planning examples, LLMs generate an initial plan, τ 0 s . This plan uses object categories instead of specific IDs due to LLM input capacity limitations.

Semantic Grounding and Refinement (SGR). The SGR step refines the initial plan τ 0 s by correcting invalid or ambiguous terms (e.g., "walk kitchencounter" to "walk kitchen" because "kitchencounter" is absent). It computes cosine similarities (cos(θ) = ⃗a·⃗b |⃗a||⃗b| ) between plan element embeddings (a) and environmental component embeddings (b). Invalid terms are then substituted with the closest valid environmental actions or objects. This yields a semantically refined plan, τs, ready for ASP reasoning and execution.

5.2 Enhancing a Skeleton Plan by ASP

The skeleton plan τs is refined using ASP to establish action dependencies and specify object locations. First, reusable ASP codes encode robotic action models (e.g., cause-effect relationships). ASP's initial state is then derived from a global environment map-a directed acyclic graph of entity nodes and relationship edges (e.g., is(1,character), state(7,dirty), relation(in,5,2)). Finally, a Python module translates τs into ASP rules, treating each subtask as a temporally ordered goal to produce the final plan τf . This process is detailed in Section 4.

6 Evaluation

6.1 Experiment Setup

Simulator and Dataset.

Experiments utilize the VirtualHome (VH) simulator v2.3.0, where an agent interacts with 250-300 household objects using 42 actions. These objects, linked by approximately 3,000 relationships, form an environment abstracted as a grounded directed acyclic graph. As shown in Fig. 1, task inputs comprise a natural language description (task), the environment as a serialized dictionary (Env.), and structured possible actions (Act.). Each task instance includes a reference plan-the ground truth sequence of verb-object pairs that accomplishes the task. (e.g., [WALK] <wardrobe>, [GRAB] <clothes>, [PUTIN] <clothes><clothesbin>for "put clothes in bin"). For evaluation, we sample 269 of 292 VH task instances and reserve 23 for prompting examples.

LLMs and Solvers. Evaluations of CLMASP and baselines utilize the LLMs gpt-3.5-turbo-1106 [Brown et al., 2020], gpt-4o-2024-08-06 [Hurst et al., 2024], and Llama3.1-8B [Meta AI, 2024]. For its ASP solver, CLMASP employed clingo 5.7.1 [Gebser et al., 2019] and DLV2 [Calimeri et al., 2022]. The SGR step in CLMASP used the textembedding-ada-002 embedding model. To ensure fairness, all experimental results in this paper are obtained from actual measurements rather than citations.

Metrics. Metrics include ASP Planning Time (TASP), the ASP runtime (Fig. 1, lower part); Solvability Rate (Rsol), the proportion of instances where the final plan τf is successfully solved; Executability Rate (Rexec), the portion of τf successfully executed in VH; and Final Plan Length Stats (Lτf ), covering average, median, and maximum τf length. We also measure Mean Goal Condition Recall (GCR), averaged across all instances. For each instance, GCR is the proportion of goal states and relations achieved:

where Dinitial, Dmethod, and Dgoal are the sets of object states and relations at the initial state, after method application, and in the goal state, respectively.

6.2 Results and Analysis

To verify CLMASP's effectiveness, we compare it with three baselines. As shown in Table 1, CLMASP's Rexec (90%) and GCR (42%) significantly surpass the best baseline (33% and 27%, respectively), indicating CLMASP effectively improves executability and goal condition fulfillment of LLM-based planning in large domains.

To assess the contribution of CLMASP's two ASP planning acceleration techniques, we conduct an ablation study. As shown in Table 2, removing loop-admissible reduction (-R) results in TASP exceeding 2 hours; including it drops solving time below 40 seconds. Adding the skeleton plan technique further improves solving efficiency by 24%-87% and significantly increases Rsol by approximately 58%-86%. The method is effective for Lτf across different LLMs and solvers. Therefore, these two techniques, especially the reduction technique, are crucial for accelerating ASP planning and key to its practicality.

To verify the necessity of CLMASP's dual-phase approach, we also conduct an ablation study. As shown in Table 3, removing the ASP solving step leads to plans with only 3.7%- 27.1%Rexec. In contrast, removing SGR still maintains 39%- 87% Rexec. However, only when both components are included does the method achieve 89.59% Rexec and around 40% average GCR. Thus, the ASP solving step is CLMASP's core phase, while SGR serves as a powerful enhancement to fully exploit its potential by correcting the grounding and utilization of objects.

A horizontal comparison in Table 2 and 3 reveals that while clingo and DLV2 offer similar ASP solving capabilities, clingo is more efficient. Regarding LLMs, their performance mainly dictates skeleton plan quality, which impacts GCR more significantly (sometimes negatively) than Rexec.

7 Conclusion

This paper defines the planning problem with a skeleton plan and encodes the ASP program to refine the skeleton plan to accomplish the task. We introduce admissible and safe reductions that preserve solutions, and to address the challenge of identifying them, we propose a sufficient condition for admissible reductions using loops and loop formulas. Using these speedup techniques, we present CLMASP, an approach coupling LLMs with ASP for robotic task planning. Experiments on the VirtualHome platform demonstrate CLMASP's improvements in both computational efficiency and plan executable rates.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 62332016), the Key Research Program of Frontier Sciences, CAS (No. ZDBS-LYJSC001), the National Key R&D Program of China (No. 2023YFB4704500), and the Hunan Province Major Scientific and Technological Project (No. 2024QK200).

Contribution Statement

The first two authors contributed equally to this work.