# Learning adaptive planning representations with natural language guidance

Lionel Wong1 Jiayuan Mao1* Pratyusha Sharma1* Zachary S. Siegel2 Jiahai Feng3
Noa Korneev4 Joshua B. Tenenbaum1 Jacob Andreas1
1MIT 2Princeton University 3UC Berkeley 4Microsoft
Asterisk indicates equal contribution. Correspondence to<EMAIL_ADDRESS>Code
for this paper will be released upon publication.

###### Abstract

Effective planning in the real world requires not only world knowledge, but
the ability to leverage that knowledge to build the right representation of
the task at hand. Decades of hierarchical planning techniques have used
domain-specific temporal action abstractions to support efficient and accurate
planning, almost always relying on human priors and domain knowledge to
decompose hard tasks into smaller subproblems appropriate for a goal or set of
goals. This paper describes Ada (Action Domain Acquisition), a framework for
automatically constructing task-specific planning representations using task-
general background knowledge from language models (LMs). Starting with a
general-purpose hierarchical planner and a low-level goal-conditioned policy,
Ada interactively learns a library of planner-compatible high-level action
abstractions and low-level controllers adapted to a particular domain of
planning tasks. On two language-guided interactive planning benchmarks (Mini
Minecraft and ALFRED Household Tasks), Ada strongly outperforms other
approaches that use LMs for sequential decision-making, offering more accurate
plans and better generalization to complex tasks.

##  1 Introduction

People make complex plans over long timescales, flexibly adapting what we know
about the world in general to govern how we act in specific situations. To
make breakfast in the morning, we might convert a broad knowledge of cooking
and kitchens into tens of fine-grained motor actions in order to find, crack,
and fry a specific egg; to achieve a complex research objective, we might plan
a routine over days or weeks that begins with the low-level actions necessary
to ride the subway to work. The problem of adapting general world knowledge to
support flexible long-term planning is one of the unifying challenges of AI.
While decades of research have developed representations and algorithms for
solving restricted and shorter-term planning problems, generalized and long-
horizon planning remains a core, outstanding challenge for essentially all AI
paradigms, including classical symbolic planning (Erol et al., 1994),
reinforcement learning (Sutton et al., 1999), and modern generative AI (Wang
et al., 2023a).

How do humans solve this computational challenge? A growing body of work in
cognitive science suggests that people come up with hierarchical, problem-
specific representations of their actions and environment to suit their goals,
tailoring how they represent, remember, and reason about the world to plan
efficiently for a particular set of tasks (e.g., Ho et al., 2022). In AI, a
large body of work has studied hierarchical planning using domain-specific
temporal abstractions—progressively decomposing high-level goals into
sequences abstract actions that eventually bottom out in low-level control. An
extensive body of work has explored how to plan using these hierarchical
action spaces, including robotic task-and-motion planning (TAMP) systems
(Garrett et al., 2021) and hierarchical RL frameworks (Sutton et al., 1999).

However, identifying a set of abstract actions that are relevant and useful
for achieving any given set of goals remains the central bottleneck in general
hierarchical planning. Intuitively, “useful” high-level actions must satisfy
many different criteria: they should enable time-efficient high-level
planning, correspond feasible low-level action sequences, and compose and
generalize to new tasks. Despite efforts to learn high-level actions
automatically in both classical planning (Nejati et al., 2006) and RL
formulations (Dietterich, 2000), most state-of-the-art robotics and planning
systems rely on human expertise to hand-engineer new planning representations
for each new domain (Ahn et al., 2022).

Figure 1: Our approach solves complex planning tasks specified in language and
grounded in interactive environments by jointly learning a library of symbolic
high-level action abstractions and modular low-level controllers associated
with each abstraction. Our system leverages background information in language
as a prior to propose useful action abstractions, then uses a hierarchical
planning framework to verify and ground them.

In this paper, we introduce Action Domain Acquisition (Ada), a framework for
using background knowledge from language (conveyed via language models) as an
initial source of task-relevant domain knowledge. Ada uses language models
(LMs) in an interactive planning loop to assemble a library of composable,
hierarchical actions tailored to a given environment and task space. Each
action consists of two components: (1) a high-level abstraction represented as
a symbolic planning operator (Fikes & Nilsson, 1971) that specifies
preconditions and action effects as sets of predicates; and (2) a low-level
controller that can achieve the action’s effects by predicting a sequence of
low-level actions with a neural network or local search procedure. We study
planning in a multitask reinforcement learning framework, in which agents
interact with their environments to must solve collections of tasks of varying
complexity. Through interaction, Ada builds up a library of actions
incrementally, at each step ensuring that learned high-level actions compose
to produce valid abstract plans and realizable low-level trajectories.

We evaluate Ada (Fig. 1) on two benchmarks, Mini Minecraft and ALFRED
(Shridhar et al., 2020). We compare this approach against three baselines that
leverage LMs for sequential decision-making in other ways: to parse linguistic
goals into formal specifications that are solved directly by a planner (as in
Liu et al. (2023)), to directly predict sequences of high-level subgoals (as
in Ahn et al. (2022)), and to predict libraries of actions defined in general
imperative code (as in Wang et al. (2023a)). In both domains, we show that Ada
learns action abstractions that allow it to solve dramatically more tasks on
each benchmark than these baselines, and that these abstractions compose to
enable efficient and accurate planning in complex, unseen tasks.

##  2 Problem Formulation

We assume access to an environment
$\langle{\mathcal{X}},{\mathcal{U}},{\mathcal{T}}\rangle$, where
${\mathcal{X}}$ is the (raw) state space, ${\mathcal{U}}$ is the (low-level)
action space (e.g., robot commands), and ${\mathcal{T}}$ is a deterministic
transition function
${\mathcal{T}}:{\mathcal{X}}\times{\mathcal{U}}\rightarrow{\mathcal{X}}$. We
also have a set of features (or “predicates”) ${\mathcal{P}}$ that define an
abstract state space ${\mathcal{S}}$: each abstract state $s\in{\mathcal{S}}$
is composed of a set of objects and their features. For example, a simple
scene that contains a red box on a table could be represented by an abstract
state containing two objects A and B, and a set of atoms
$\\{\textit{red}(\text{A}),\textit{box}(\text{A}),\textit{table}(\text{B}),\textit{on}(\text{A},\text{B})\\}$.
We assume the mapping from environmental states to abstract states
$\Phi:{\mathcal{X}}\rightarrow{\mathcal{S}}$ is given and fixed (though see
Migimatsu & Bohg, 2022 for how it might be learned).

Figure 2: Representation for our (a) task input, (b) the bi-level planning and
execution pipeline for inference time, and (c) the abstract state and action
representation. Figure 3: The overall framework. Given task environment states
and descriptions, at each iteration, we first propose candidate abstract
actions (operators) ${\mathcal{A}}_{i}^{\prime}$, then uses bi-level planning
and execution to solve tasks. We add operators to the operator library based
on the execution result.

In addition to the environment, we have a collection of tasks $t$. Each $t$ is
described by a natural language instruction $\ell_{t}$, corresponding to a
goal predicate (which is not directly observed). In this paper, we assume that
predicates may be defined in terms of abstract states, i.e.,
$g_{t}:{\mathcal{S}}\rightarrow\\{T,F\\}$. Our goal is to build an agent that,
given the initial state $x_{0}\in{\mathcal{X}}$ and the natural language
instruction $\ell_{t}$, can generate a sequence of low-level actions
$\\{u_{1},u_{2},\cdots,u_{H}\\}\in{\mathcal{U}}^{H}$ such that
$g_{t}(\Phi(x_{H}))$ is true (where $x_{H}$ is the terminal state of
sequentially applying $\\{u_{i}\\}$ on $x_{0}$). The agent receives reward
signal only upon achieving the goal specified by $g_{t}$.

Given a very large number of interactions, a sufficiently expressive reflex
policy could, in principle, learn a policy that maps from low-level states to
low-level actions conditioned on the language instruction $\pi(u\mid
x;\ell_{t})$. However, for very long horizons $H$ and large state spaces
(e.g., composed of many objects and compositional goals), such algorithms can
be highly inefficient or effectively infeasible. The key idea behind our
approach is to use natural language descriptions $\ell_{t}$ to bootstrap a
high-level action space ${\mathcal{A}}$ over the abstract state space
${\mathcal{S}}$ to accelerate learning and planning.

Formally, our approach learns a library of high-level actions (also called
operators in classical planning) ${\mathcal{A}}$. As illustrated in Fig. 2b,
each $a\in{\mathcal{A}}$ is a tuple of
$\langle\textit{name},\textit{args},\textit{pre},\textit{eff},\textit{controller}\rangle$.
name is the name of the action, args is a list of variables, usually denoted
by $?x,?y,etc.\hbox{}$, pre is a precondition formula based on the variables
args and the features ${\mathcal{P}}$, and eff is the effect, which is also
defined in terms of args and ${\mathcal{P}}$. Finally,
$\textit{controller}:{\mathcal{X}}\rightarrow{\mathcal{U}}$ is a low-level
policy associated with the action. The semantics of the preconditions and
effects is: for any state $x$ such that $\textit{pre}(\Phi(x))$, executing
controller starting in $x$ (for an indefinite number of steps) will yield a
state $x^{\prime}$ such that $\textit{eff}(\Phi(x^{\prime}))$ (Lifschitz,
1986). In this framework, ${\mathcal{A}}$ defines a partial, abstract world
model of the underlying state space.

As shown in Fig. 2b, given the set of high-level actions and a parse of the
instruction $\ell_{t}$ into a first-order logic formula, we can leverage
symbolic planners (e.g., Helmert, 2006) to first compute a high-level plan
$\\{a_{1},\cdots,a_{K}\\}\in{\mathcal{A}}^{K}$ that achieves the goal
$\ell_{t}$ symbolically, and then refine the high-level plan into a low-level
plan leveraging the controllers associated with each action. This bi-level
planning approach decomposes long-horizon planning problems into several
short-horizon problems. Furthermore, it can also leverage the compositionality
of high-level actions ${\mathcal{A}}$ to generalize to longer plans.

##  3 Action Abstractions from Language

As illustrated in Fig. 3, our framework, Action Domain Acquisition (Ada)
learns action abstractions iteratively as it attempts to solve tasks. Our
algorithm is given a dataset of tasks and their corresponding language
descriptions, the feature set ${\mathcal{P}}$, and optionally an initial set
of high-level action operators ${\mathcal{A}}_{0}$. At each iteration $i$, we
first use a large language model (LLM) to propose a set of novel high-level
action definitions ${\mathcal{A}}_{i}^{\prime}$ based on the features
${\mathcal{P}}$ and the language goals $\\{\ell_{t}\\}$ (Section 3.1). Next,
we use a LLM to also translate each language instruction $\ell_{t}$ into a
symbolic goal description $F_{t}$, and use a bi-level planner to compute a
low-level plan to accomplish $\ell_{t}$ (Section 3.2). Then, based on the
planning and execution results, we score each operator in ${\mathcal{A}}_{i}$
and add ones to the verified library if they have yielded successful execution
results (Section 3.4). To accelerate low-level planning, we simultaneously
learn local subgoal-conditioned policies (i.e., the controllers for each
operator; Section 3.3). Algorithm 1 summarizes the overall framework.

A core goal of our approach is to adapt the initial action abstractions
proposed from an LLM prior into a set of useful operators ${\mathcal{A}}*$
that permit efficient and accurate planning on a dataset of tasks and ideally,
that generalize to future tasks. While language provides a key initial prior,
our formulation refines and verifies the operator library to adapt to a given
planning procedure and environment (similar to other action-learning
formulations like Silver et al., 2021). Our formulation ensures not only that
the learned operators respect the dynamics of the environment, but also fit
their grain of abstraction according to the capacity of the controller,
trading off between fast high-level planning and efficient low-level control
conditioned on each abstraction.

Algorithm 1 Action Abstraction Learning from Language

1:Dataset of tasks and their language descriptions $\\{\ell_{t}\\}$

2:Predicate set ${\mathcal{P}}$

3:Optionally, an initial set of abstract operators ${\mathcal{A}}_{0}$, or
${\mathcal{A}}_{0}=\emptyset$

4:Initialize subgoal-conditioned policy $\pi_{\theta}$.

5:for $i=1,2,\cdots,M$ do

6:
${\mathcal{A}}_{i}\leftarrow{\mathcal{A}}_{i-1}\cup\text{ProposeOperatorDefinitions}({\mathcal{P}},\\{\ell_{t}\\})$
$\triangleright$ Section 3.1

7: for each unsolved task $j$: $(x^{(j)}_{0},\ell^{(j)}_{t})$ do

8: $\bar{u}\leftarrow\text{BiLevelPlan}({\mathcal{A}}_{i},\ell^{(j)}_{t},\pi)$
$\triangleright$ Section 3.2

9: $\textit{result}^{(j)}\leftarrow\text{Execute}(x^{(j)}_{0},\bar{u})$
$\triangleright$ Execute the plan

10: $\theta\leftarrow\text{UpdateSubgoalPolicy}(\theta,\textit{result})$
$\triangleright$ Section 3.3

11:
${\mathcal{A}}_{i}\leftarrow\text{ScoreAndFilter}({\mathcal{A}}_{i},\textit{result})$
$\triangleright$ Section 3.4 return ${\mathcal{A}}_{M}$

Figure 4: Our two-stage prompting method for generating candidate operator
definitions. (a) Given a task instruction, we first prompt an LLM to generate
a candidate symbolic task decomposition. (b) We then extract undefined
operator names that appear in these action sequences and prompt an LLM to
generate symbolic definitions.

###  3.1 Operator Proposal

${\mathcal{A}}_{i}\leftarrow{\mathcal{A}}_{i-1}\cup\text{ProposeOperatorDefinitions}({\mathcal{P}},\\{\ell_{t}\\})$

At each iteration $i$, we use a pretrained LLM to extend the previous operator
library ${\mathcal{A}}_{i-1}$ with a large set of candidate operator
definitions proposed by the LLM based on the task language descriptions and
environment features ${\mathcal{P}}$. This yields an extended candidate
library ${\mathcal{A}}_{i}^{\prime}$ where each
$a\in{\mathcal{A}}_{i}^{\prime}=\langle\textit{name},\textit{args},\textit{pre},\textit{eff}\rangle$
where name is a human-readable action name and
$\textit{args},\textit{pre},\textit{eff}$ are a PDDL operator definition. We
employ a two-stage prompting strategy: symbolic task decomposition followed by
symbolic operator definition.

Example. Fig. 4 shows a concrete example. Given a task instruction (Bring a
hot egg to the table) and the abstract state description, we first prompt the
LLM to generate an abstract task decomposition, which may contain operator
names that are undefined in the current operator library. Next, we extract the
names of those undefined operators and prompt LLMs to generate the actual
symbolic operator descriptions, in this case, the new heat-object operator.

Symbolic task decomposition. For a given task $\ell_{t}$ and a initial state
$x_{0}$, we first translate the raw state $x_{0}$ into a symbolic description
$\Phi(x_{0})$. To constrain the length of the state description, we only
include unary features in the abstract state (i.e., only object categories and
properties). Subsequently, we present a few-shot prompt to the LLM and query
it to generate a proposed task decomposition conditioned on the language
description $\ell_{t}$. It generates a sequence of named high-level actions
and their arguments, which explicitly can include high-level actions that are
not yet defined in the current action library. We then extract all the
operator names proposed across tasks as the candidate high-level operators.
Note that while in principle we might use the LLM-proposed task decomposition
itself as a high-level plan, we find empirically that this is less accurate
and efficient than a formal planner.

Symbolic operator definition. With the proposed operator names and their usage
examples (i.e., the actions and their arguments in the proposed plans), we
then few-shot prompt the LLM to generate candidate operator definitions in the
PDDL format (argument types, and pre/postconditions defined based on features
in ${\mathcal{P}}$). We also post-process the generated operator definitions
to remove feature names not present in ${\mathcal{P}}$ and correct syntactic
errors. We describe implementation details for our syntax correction strategy
in the appendix.

###  3.2 Goal Proposal and Bi-Level Planning

foreach unsolved task $(x^{(j)}_{0},\ell^{(j)}_{t})$:
$\displaystyle\qquad\bar{u}\leftarrow\text{BiLevelPlan}({\mathcal{A}}_{i},\ell^{(j)}_{t},\pi)$
$\displaystyle\qquad\textit{result}^{(j)}\leftarrow\text{Execute}(x^{(j)}_{0},\bar{u})$

At each iteration $i$, we then attempt to BiLevelPlan for unsolved tasks in
the dataset. This step attempts to find and execute a low-level action
sequence $\\{u_{1},u_{2},\cdots,u_{H}\\}\in{\mathcal{U}}^{H}$ for each task
using the proposed operators in ${\mathcal{A}}_{i}^{\prime}$ that satisfies
the unknown goal predicate $g_{t}$ for each task. This provides the
environment reward signal for action learning. Our BiLevelPlan implementation
uses standard hierarchical planning tools as follows:

Symbolic goal proposal: As defined in Sec. 2, each task is associated with a
queryable but unknown goal predicate $g_{t}$ that can be represented as a
first-order logic formula $f_{t}$ over symbolic features in ${\mathcal{P}}$.
Our agent only has access to a linguistic task description $\ell_{t}$, so we
use a few-shot prompted LLM to predict candidate goal formulas
$F_{t}^{\prime}$ conditioned on $\ell_{t}$ and features ${\mathcal{P}}$.

High-level planning: Given each candidate goal formula $f_{t}^{\prime}\in
F_{t}^{\prime}$, the initial abstract problem state $s_{0}$, and the current
candidate operator library ${\mathcal{A}}^{\prime}$, we search for a high-
level plan $P_{A}=\\{(a_{1},o_{1_{i}}...),\cdots,(a_{K},o_{K_{i}}...)\\}$ as a
sequence of high-level actions from ${\mathcal{A}}^{\prime}$ concretized with
object arguments $o$, such that executing the action sequence would satisfy
$f_{t}^{\prime}$ according to the operator definitions. This is a standard
symbolic PDDL planning formulation; we use an off-the-shelf symbolic planner,
FastDownward (Helmert, 2006) to find high-level plans.

Low-level planning and environment feedback: We then search for a low-level
plan as a sequence of low-level actions
$\\{u_{1},u_{2},\cdots,u_{H}\\}\in{\mathcal{U}}^{H}$, conditioned on the high-
level plan structure. Each concretized action tuple $(a_{i},o_{1_{i}}...)\in
P_{A}$ defines a local subgoal $sg_{i}$, as the operator postcondition
parameterized by the object arguments $o$. For each $(a_{i},o_{1_{i}}...)\in
P_{A}$, we therefore search for a sequence of low-level actions
$u_{i_{1}},u_{i_{2}}...$ that satisfies the local subgoal $sg_{i}$. We search
with a fixed budget per subgoal, and fail early if we are unable to satisfy
the local subgoal $sg_{i}$. If we successfully find a complete sequence of
low-level actions satisfying all local subgoals $sg_{i}$ in $P_{A}$, we
execute all low-level actions and query the hidden goal predicate $g_{t}$ to
determine environment reward. We implement a basic learning procedure to
simultaneously learn subgoal-conditioned controllers over time (described in
Section 3.3), but our formulation is general and supports many hierarchical
planning schemes (such as sampling-based low-level planners (LaValle, 1998) or
RL algorithms).

###  3.3 Policy Learning and Guided Low-Level Search

$\theta\leftarrow\text{UpdateSubgoalPolicy}(\theta,\textit{result})$

The sequence of subgoals $sg_{i}$ corresponding to high-level plans $P_{A}$
already restricts the local low-level planning horizon. However, we further
learn subgoal-conditioned low-level policies $\pi(u|x;\textit{sg})$ from
environment feedback during training to accelerate low-level planning. To
exploit shared structure across subgoals, we learn a shared controller for all
operators from $x\in{\mathcal{X}}$ and conjunctions of predicates in $sg$. To
maximize learning during training, we use a hindsight goal relabeling scheme
(Andrychowicz et al., 2017), supervising on all conjunctions of predicates in
the state as we roll out low-level search. While the shared controller could
be learned as a supervised neural policy, we find that our learned operators
sufficiently restrict the search to permit learning an even simpler count-
based model from $X,sg\rightarrow u\in{\mathcal{U}}$. We provide additional
details in the Appendix.

###  3.4 Scoring LLM Operator Proposals

${\mathcal{A}}_{i}\leftarrow\text{ScoreAndFilter}({\mathcal{A}}_{i},\textit{result})$

Finally, we update the learned operator library ${\mathcal{A}}_{i}$ to retain
candidate operators that were useful and successful in bi-level planning.
Concretely, we estimate operator candidate
$a_{i}^{\prime}\in{\mathcal{A}}_{i}^{\prime}$ accuracy across the bi-level
plan executions as $s/b$ where $b$ counts the total times $a_{i}^{\prime}$
appeared in a high-level plan and $s$ counts successful execution of the
corresponding low-level action sequence to achieve the subgoal associated with
$a_{i}^{\prime}$. We retain operators if $b>\tau_{b}$ and $s/b>\tau_{r}$,
where $\tau_{b},\tau_{r}$ are hyperparameters. Note that this scoring
procedure learns whether operators are accurate and support low-level planning
independently of whether the LLM-predicted goals $f_{t}^{\prime}$ matched the
true unknown goal predicates $g_{t}$.

##  4 Experiments

Domains. We evaluate our approach on two-language specified planning-
benchmarks: Mini Minecraft and ALFRED (Shridhar et al., 2020).

Mini Minecraft (Fig. 5, top) is a procedurally-generated Minecraft-like
benchmark (Chen et al., 2021; Luo et al., 2023) that requires complex,
extended planning. The environment places an agent on a 2D map containing
various resources, tools, and crafting stations. The agent can use appropriate
tools to mine new items from raw resources (e.g. use an axe to obtain wood
from trees), or collect resources into an inventory to craft new objects (e.g.
combining sticks and iron ingots to craft a sword, which itself can be used to
obtain feathers from a chicken). The ability to create new objects that
themselves permit new actions yields an enormous action space at each time
step ($>$2000 actions, considering different combinations of items to use) and
very long-horizon tasks (26 steps for the most complex task, even without
path-planning.) The provided environment predicates allow querying object
types and inventory contents. Low-level actions allow the agent to move and
apply tools to specific resources. To focus on complex crafting, we provide a
low-level move-to action to move directly to specified locations. Linguistic
goal specifications are synthetically generated from a simple grammar over
craftable objects and resources (e.g. Craft a sword, Mine iron ore).

ALFRED (Fig. 5, bottom) is a household planning benchmark of human-annotated
but formally verifiable tasks defined over a simulated Unity environment
(Shridhar et al., 2020). The interactive environment places an agent in
varying 3D layouts, each containing appliances and dozens of household
objects. The provided environment includes predicates for querying object
types, object and agent locations, and classifiers over object states (eg.
whether an object is hot or on). Low-level actions enable the agent to pick up
and place objects, apply tools to other objects, and open, close, and turn on
appliances. As specified in Shridhar et al. (2020), ground-truth high-level
plans in the ALFRED benchmark compose 5-10 high-level operators, and low-level
action trajectories have on average 50 low-level actions. There over 100
objects that the agent can interact with in each interactive environment.

As with Minecraft, we provide a low-level method to move the agent directly to
specified locations. While ALFRED is typically used to evaluate detailed
instruction following, we focus on a goal-only setting that only uses the goal
specifications. The human-annotated goals introduce ambiguity,
underspecification, and errors with respect to the ground-truth verifiable
tasks (eg. people refer to tables without specifying if they mean the side
table, dining table, or desk; a light when there are multiple distinct lamps;
or a cabbage when they want lettuce).

Figure 5: Top: (a) Visualization of the Mini Minecraft environment, showing an
intermediate step towards crafting a bed. (b) Operator proposed by an LLM and
verified by our algorithm through planning and execution. (c) Visualization of
the low-level crafting tools involved in crafting the bed. Bottom: (a)
Visualization of the ALFRED household environment. (b) Example operators
proposed by LLM and verified by our algorithm, which are composed to solve the
cold potato slice task.

Experimental setup. We evaluate in an iterative continual learning setting;
except on the compositional evaluations, we learn from n=2 iterations through
all (randomly ordered) tasks and report final accuracy on those tasks. All
experiments and baselines use GPT-3.5. For each task, at each iteration, we
sample n=4 initial goal proposals and n=4 initial task decompositions, and n=3
operator definition proposals for each operator name. We report best-of
accuracy, scoring a task as solved if verification passes on at least one of
the proposed goals. For Minecraft, we set the motion planning budget for each
subgoal to $\leq$1000 nodes. For ALFRED, which requires a slow Unity
simulation, we set it to 50 nodes. Additional temperature and sampling details
are in the Appendix.

We evaluate on three Mini Minecraft benchmark variations to test how our
approach generalizes to complex, compositional goals. In the simplest Mining
benchmark, all goals involve mining a target item from an appropriate initial
resource with an appropriate tool (e.g., Mining iron from iron_ore with an
axe), and require learning which tools can be used to obtain which items. In
the harder Crafting benchmark, goals involve crafting a target artifact (e.g.,
a bed), which may require mining a few target resources. The most challenging
Compositional benchmark combines mining and crafting tasks, in environments
that only begin with raw resources and two starting tools (axe and pickaxe).
Agents may need to compose multiple skills to obtain other downstream
resources (see Fig. 5 for an example). To test action generalization, we
report evaluation on the Compositional using only actions learned previously
in the Mining and Crafting benchmarks.

We similarly evaluate on an ALFRED benchmark of Simple and Compositional tasks
drawn from the original task distribution in Shridhar et al. (2020). This
distribution contains simple tasks that require picking up an object and
placing it in a new location, picking up objects, applying a single household
skill to an object and moving them to a new location (e.g., Put a clean apple
on the dining table), and compositional tasks that require multiple skills
(e.g., Place a hot sliced potato on the counter). We use a random subset of
n=223 tasks, selected from an initial 250 that we manually filter to remove
completely misspecified goals (which omit any mention of the target object or
skill).

Baselines. We compare our method to three baselines, each related to language-
guided planning systems in recent work.

Low-level Planning Only uses an LLM to predict only the symbolic goal
specification conditioned on the high-level predicates and linguistic goal,
then uses the low-level planner to search directly for actions that satisfy
that goal. This baseline implements a model like LLM+P (Liu et al., 2023),
which uses LLMs to translate linguistic goals into planning-compatible formal
specifications, then attempt to plan directly towards these with no additional
representation learning.

Subgoal Prediction uses an LLM to predict a sequence of high-level subgoals
(as PDDL pre/postconditions with object arguments), conditioned on the high-
level predicates, and task goal and initial environment state. This baseline
implements a model like SayCan (Ahn et al., 2022), which uses LLMs to directly
predict goal and a sequence of decomposed formal subgoal representations, then
applies low-level planning over these formal subgoals.

Code Policy Prediction uses an LLM to predict the definitions of a library of
imperative local code policies in Python (with cases and control flow) over an
imperative API that can query state and execute low-level actions.) Then, as
FastDownward planning is no longer applicable, we also use the LLM to predict
the function call sequences with arguments for each task. This baseline
implements a model like Voyager (Wang et al., 2023a), which uses an LLM to
predict a library of skills implemented as imperative code and to directly
predict a sequence of these skills to solve individual tasks. Like Voyager, we
verify the individual code skills during interactive planning, but do not use
a more global learning objective to attempt to learn a concise or non-
redundant library.

###  4.1 Results

Mini Minecraft (n=3) | LLM Predicts? | Library? | Mining | Crafting | Compositional
---|---|---|---|---|---
Low-level Planning Only | Goal | ✗ | 31% ($\sigma$=0.0%) | 9% ($\sigma$=0.0%) | 9% ($\sigma$=0.0%)
Subgoal Prediction | Sub-goals | ✗ | 33% ($\sigma$=1.6%) | 36% ($\sigma$=5.6%) | 6% ($\sigma$=1.7%)
Code Policy Prediction | Sub-policies | ✓ | 15% ($\sigma$=1.2%) | 39% ($\sigma$=3.2%) | 10% ($\sigma$=1.7%)
Ada (Ours) | Goal+Operators | ✓ | 100% ($\sigma$=0.0%) | 100% ($\sigma$=7.5%) | 100% ($\sigma$=4.1%)
ALFRED (n=3 replications) | LLM Predicts? | Library? | Original (Simple + Compositional Tasks)
Low-level Planning Only | Goal | ✗ | 21% ($\sigma$=1.0%)
Subgoal Prediction | Sub-goal | ✗ | 2% ($\sigma$=0.4%)
Code Policy Prediction | Sub-policies | ✓ | 2% ($\sigma$=0.9%)
Ada (Ours) | Goal+Operators | ✓ | 79% ($\sigma$=0.9%)

Table 1: (Top) Results on Mini Minecraft. Our algorithm successfully recovers
all intermediate operators for mining and crafting, which enable
generalization to more compositional tasks (which use up to 26 operators)
without any additional learning. (Bottom) Results on ALFRED. Our algorithm
recovers all required household operators, which generalize to more complex
compositional tasks. All results report mean performance and STD from n=3
random replications for all models.

What action libraries do we learn? Fig. 5 shows example operators learned on
each domain (Appendix A.2 contains the full libraries of operators learned on
both domains from a randomly sampled run of the n=3 replications). In Mini
Minecraft, we manually inspect the library and find that we learn operators
that correctly specify the appropriate tools, resources, and outputs for all
intermediate mining actions (on Mining) and crafting actions (on Crafting),
allowing perfect direct generalization to the Compositional tasks without any
additional training on these complex tasks. In ALFRED, we compare the learned
libraries from all runs to the ground-truth operator library hand-engineered
in Shridhar et al. (2020). The ground-truth operator set contains 8 distinct
operators corresponding to different compositional skills (eg. Slicing,
Heating, Cleaning, Cooling). Across all replications, model reliably recovers
semantically identical (same predicate preconditions and postconditions)
definitions for all of these ground-truth operators, except for a single
operator that is defined disjunctively (the ground-truth Slice skill specifies
either of two types of knives), which we occasionally learn as two distinct
operators or only recover with one of these two types.

We also inspect the learning trajectory and find that, through the interactive
learning loop, we successfully reject many initially proposed operator
definitions sampled from the language model that turn out to be redundant
(which would make high-level planning inefficient), inaccurate (including
apriori reasonable proposals that do not fit the environment specifications,
such as proposing to clean objects with just a towel, when our goal verifiers
require washing them with water in a sink), or underspecified (such as those
that omit key preconditions, yielding under-decomposed high-level task plans
that make low-level planning difficult).

Do these actions support complex planning and generalization? Table 2 shows
quantitative results from n=3 randomly-initialized replications of all models,
to account for random noise in sampling from the language model and
stochasticity in the underlying environment (eg. in the Unity environment in
ALFRED). On Minecraft, where goal specification is completely clear due to the
synthetic language, we solve all tasks in each evaluation variation, including
the challenging Compositional setting — the action libraries learned from
simpler mining/crafting tasks generalize completely to complex tasks that
require crafting all intermediate resources and tools from scratch. On ALFRED,
we vastly outperform all other baselines, demonstrating that the learned
operators are much more effective for planning and compose generalizably to
more complex tasks. We qualitatively find that failures on ALFRED occur for
several reasons. One is goal misspecification, when the LLM does not
successfully recover the formal goal predicate (often due to ambiguity in
human language), though we find that on average, 92% of the time, the ground
truth goal appears as one of the top-4 goals translated by the LLM. We also
find failures due to low-level policy inaccuracy, when the learned policies
fail to account for low-level, often geometric details of the environment (eg.
the learned policies are not sufficiently precise to place a tall bottle on an
appropriately tall shelf). More rarely, we see planning failures caused by
slight operator overspecification (eg. the Slice case discussed above, in
which we do not recover the specific disjunction over possible knives that can
be used to slice.) Both operator and goal specification errors could be
addressed in principal by sampling more (and more diverse) initial proposals.

How does our approach compare to using the LLM to predict just goals, or
predict task sequences? As shown in Table 2, our approach vastly outperforms
the Low-level Planning Only baseline on both domains, demonstrating the value
of the action library for longer horizon planning. We also find a substantial
improvement over the Subgoal Prediction baseline. While the LLM frequently
predicts important high-level aspects of the task subgoal structure (as it
does to propose operator definitions), it frequently struggles to robustly
sequence these subgoals and predict appropriate concrete object groundings
that correctly obey the initial problem conditions or changing environment
state. These errors accumulate over the planning horizon, reflected in
decreasing accuracy on the compositional Minecraft tasks (on ALFRED, this
baseline struggles to solve any more than the basic pick-and-place tasks, as
the LLM struggles to predict subgoals that accurately track whether objects
are in appliances or whether the agent’s single gripper is full with an
existing tool.)

How does our approach compare to using the LLM to learn and predict plans
using imperative code libraries? Somewhat surprisingly, we find that the Code
Policy prediction baseline performs unevenly and often very poorly on our
benchmarks. (We include additional results in A.1.1 showing that our model
also dramatically outperforms this baseline using GPT-4 as the base LLM.) We
find several key reasons for the poor performance of this baseline relative to
our model, each which validate the key conceptual contributions of our
approach. First, the baseline relies on the LLM as the planner – as the skills
are written as general Python functions, rather than any planner-specific
representation, we do not use an optimized planner like FastDownward. As with
Subgoal Prediction, we find that the LLM is not a consistent or accurate
planner. While it retrieves generally relevant skills from the library for
each task, it often struggles to sequence them accurately or predict
appropriate arguments given the initial problem state. Second, we find that
imperative code is less suited in general as a hierarchical planning
representation for these domains than the high-level PDDL and low-level local
policy search representation we use in our model. This is because it uses
control flow to account for environment details that would otherwise be
handled by local search relative to a high-level PDDL action. Finally, our
model specifically frames the library learning objective around learning a
compact library of skills that enables efficient planning, whereas our Voyager
re-implementation (as in Wang et al. (2023a)) simply grows a library of skills
which are individually executable and can be used to solve individual, shorter
tasks. Empirically, as with the original model in Wang et al. (2023a), this
baseline learns hundreds of distinct code definitions on these datasets, which
makes it harder to accurately plan and generalize to more complex tasks. Taken
together, these challenges support our overarching library learning objective
and the need to learn action representations suited for structured
hierarchical planning.

##  5 Related Work

Planning for language goals. A large body of recent work attempts to use LLMs
to solve planning tasks specified in language. One approach is to directly
predict action sequences (Huang et al., 2022; Valmeekam et al., 2022; Silver
et al., 2022; Wang et al., 2023b), but this has yielded mixed results as LLMs
can struggle to generalize or produce correct plans as problems grow more
complex. To combat this, one line of work has explored structured and
iterative prompting regimes (e.g., ‘chain-of-thought‘ and feedback) (Mu et
al., 2023; Silver et al., 2023; Zhu et al., 2023). Increasingly, other neuro-
symbolic work uses LLMs to predict formal goal or action representations that
can be verified or solved with symbolic planners (Song et al., 2023; Ahn et
al., 2022; Xie et al., 2023; Arora & Kambhampati, 2023). These approaches
leverage the benefits of a known planning domain model. Our goal in this paper
is to leverage language models to learn this domain model. Another line of
research aims at using LLMs to generate formal planning domain models for
specific problems (Liu et al., 2023) and subsequently uses classical planners
to solve the task. However, they are not considering generating grounded or
hierarchical actions in an environment and not learning a library of operators
that can be reused across different tasks. More broadly, we share the broad
goal of building agents that can understand language and execute actions to
achieve goals (Tellex et al., 2011; Misra et al., 2017; Nair et al., 2022).
See also Luketina et al. (2019) and Tellex et al. (2020).

Learning planning domain and action representations from language. Another
group of work has been focusing on learning latent action representations from
language (Corona et al., 2021; Andreas et al., 2017; Jiang et al., 2019;
Sharma et al., 2022; Luo et al., 2023). Our work differs from them in that we
are learning a planning-compatible action abstraction from LLMs, instead of
relying on human demonstrations and annotated step-by-step instructions. The
more recent Wang et al. (2023a) adopts a similar overall problem specification
to ours, and learns libraries of actions defined as imperative code-based
policies. Our results show that learning planning abstractions enables better
integration with hierarchical planning, and, as a result, better performance
and generalization to more complex problems. Other recent work (Nottingham et
al., 2023) seeks to learn an environment world model from interactive
experience, represented as a task dependency graph; we seek to learn a richer
state transition model (which represents the effects of actions) decomposed as
operators that can be formally composed to verifiably satisfy arbitrarily
complex new goals.

Language and code. In addition to Wang et al. (2023a), a growing body of work
in program synthesis, both by learning lifted program abstractions that
compress longer existing or synthesized programs (Bowers et al., 2023; Ellis
et al., 2023; Wong et al., 2021; Cao et al., 2023). These approaches
(including Wang et al. (2023a)) generally learn libraries defined over
imperative and functional programming languages, such as LISP and Python. Our
work is closely inspired by these and seeks to learn representations suited
specifically to solving long-range planning problems.

Hierarchical planning abstractions. The hierarchical planning knowledge that
we learn from LLMs and interactions in the environments are related to
hierarchical task networks (Erol et al., 1994; Nejati et al., 2006),
hierarchical goal networks (Alford et al., 2016), abstract PDDL domains
(Konidaris et al., 2018; Bonet & Geffner, 2020; Chitnis et al., 2021; Asai &
Muise, 2020; Mao et al., 2022), and domain control knowledge (de la Rosa &
McIlraith, 2011). Most of these approaches require manually specified
hierarchical planning abstractions; others learn them from demonstrations or
interactions. By contrast, we leverage human language to guide the learning of
such abstractions.

##  6 Discussion and Future Work

Our evaluations suggest a powerful role for language within AI systems that
form complex, long-horizon plans — as a deep source of background knowledge
about the right action abstractions for everyday planning domains, which
contains broad human priors about how the world works, how to decompose tasks,
and what tasks an agent may want to solve in the future. A core goal of this
paper was to demonstrate how we might integrate knowledge in language
alongside the powerful search, grounding, and verification toolkits developed
in hierarchical planning.

We leave open many possible extensions towards future work. Key limitations of
our current framework point towards important directions for further
integrating LMs and hierarchical planning to scale our approach: here, we
build on an existing set of pre-defined symbolic predicates for initially
representing the environment state; do not yet tackle fine-grained, geometric
motor planning; and use a general LLM (rather than one fine-tuned for extended
planning). Future work might generally tackle these problems by further asking
how else linguistic knowledge and increasingly powerful or multimodal LLMs
could be integrated here: to propose useful named predicates over initial
perceptual inputs (e.g., images) (Migimatsu & Bohg, 2022); or to speed
planning by bootstrapping hierarchical planning abstractions using the
approach here, but then to progressively transfer planning to another model,
including an LLM, to later compose and use the learned representations.

## References

  * Ahn et al. (2022) Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, et al.  Do as I Can, Not as I Say: Grounding Language in Robotic Affordances.  _arXiv:2204.01691_ , 2022.
  * Alford et al. (2016) Ron Alford, Vikas Shivashankar, Mark Roberts, Jeremy Frank, and David W Aha.  Hierarchical Planning: Relating Task and Goal Decomposition with Task Sharing.  In _IJCAI_ , 2016.
  * Andreas et al. (2017) Jacob Andreas, Dan Klein, and Sergey Levine.  Modular Multitask Reinforcement Learning with Policy Sketches.  In _ICML_ , 2017.
  * Andrychowicz et al. (2017) Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Pieter Abbeel, and Wojciech Zaremba.  Hindsight Experience Replay.  In _NeurIPS_ , 2017.
  * Arora & Kambhampati (2023) Daman Arora and Subbarao Kambhampati.  Learning and Leveraging Verifiers to Improve Planning Capabilities of Pre-trained Language Models.  _arXiv:2305.17077_ , 2023.
  * Asai & Muise (2020) Masataro Asai and Christian Muise.  Learning Neural-Symbolic Descriptive Planning Models via Cube-Space Priors: The Voyage Home (To Strips).  In _IJCAI_ , 2020.
  * Bonet & Geffner (2020) Blai Bonet and Hector Geffner.  Learning First-Order Symbolic Representations for Planning from the Structure of the State Space.  In _ECAI_ , 2020.
  * Bowers et al. (2023) Matthew Bowers, Theo X Olausson, Lionel Wong, Gabriel Grand, Joshua B Tenenbaum, Kevin Ellis, and Armando Solar-Lezama.  Top-Down Synthesis for Library Learning.  _PACMPL_ , 7(POPL):1182–1213, 2023.
  * Cao et al. (2023) David Cao, Rose Kunkel, Chandrakana Nandi, Max Willsey, Zachary Tatlock, and Nadia Polikarpova.  Babble: Learning Better Abstractions with E-graphs and Anti-unification.  _PACMPL_ , 7(POPL):396–424, 2023.
  * Chen et al. (2021) Valerie Chen, Abhinav Gupta, and Kenneth Marino.  Ask Your Humans: Using Human Instructions to Improve Generalization in Reinforcement Learning.  In _ICLR_ , 2021.
  * Chitnis et al. (2021) Rohan Chitnis, Tom Silver, Joshua B Tenenbaum, Leslie Pack Kaelbling, and Tomás Lozano-Pérez.  GLiB: Efficient Exploration for Relational Model-Based Reinforcement Learning via Goal-Literal Babbling.  In _AAAI_ , 2021.
  * Corona et al. (2021) Rodolfo Corona, Daniel Fried, Coline Devin, Dan Klein, and Trevor Darrell.  Modular Networks for Compositional Instruction Following.  In _NAACL-HLT_ , 2021.
  * de la Rosa & McIlraith (2011) Tomás de la Rosa and Sheila McIlraith.  Learning Domain Control Knowledge for TLPlan and Beyond.  In _ICAPS 2011 Workshop on Planning and Learning_ , 2011.
  * Dietterich (2000) Thomas G Dietterich.  Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition.  _JAIR_ , 13:227–303, 2000.
  * Ellis et al. (2023) Kevin Ellis, Lionel Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lore Anaya Pozo, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum.  DreamCoder: Growing Generalizable, Interpretable Knowledge with Wake–Sleep Bayesian Program Learning.  _Philosophical Transactions of the Royal Society_ , 381(2251):20220050, 2023.
  * Erol et al. (1994) Kutluhan Erol, James Hendler, and Dana S Nau.  HTN Planning: Complexity and Expressivity.  In _AAAI_ , 1994.
  * Fikes & Nilsson (1971) Richard E Fikes and Nils J Nilsson.  STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving.  _Artif. Intell._ , 2(3-4):189–208, 1971.
  * Garrett et al. (2021) Caelan Reed Garrett, Rohan Chitnis, Rachel Holladay, Beomjoon Kim, Leslie Pack Kaelbling, and Tomás Lozano-Pérez.  Integrated Task and Motion Planning.  _Ann. Rev. Control Robot. Auton. Syst._ , 4:265–293, 2021.
  * Helmert (2006) Malte Helmert.  The Fast Downward Planning System.  _JAIR_ , 26:191–246, 2006.
  * Ho et al. (2022) Mark K Ho, David Abel, Carlos G Correa, Michael L Littman, Jonathan D Cohen, and Thomas L Griffiths.  People construct simplified mental representations to plan.  _Nature_ , 606(7912):129–136, 2022.
  * Huang et al. (2022) Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch.  Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents.  In _ICML_ , 2022.
  * Jiang et al. (2019) Yiding Jiang, Shixiang Shane Gu, Kevin P Murphy, and Chelsea Finn.  Language as an Abstraction for Hierarchical Deep Reinforcement Learning.  In _NeurIPS_ , 2019.
  * Konidaris et al. (2018) George Konidaris, Leslie Pack Kaelbling, and Tomas Lozano-Perez.  From Skills to Symbols: Learning Symbolic Representations for Abstract High-Level Planning.  _JAIR_ , 61:215–289, 2018.
  * LaValle (1998) Steven LaValle.  Rapidly-Exploring Random Trees: A New Tool for Path Planning.  _Research Report 9811_ , 1998.
  * Lifschitz (1986) Vladimir Lifschitz.  On the Semantics of STRIPS.  In _Workshop on Reasoning about Actions and Plans_ , 1986.
  * Liu et al. (2023) Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone.  LLM+ P: Empowering Large Language Models with Optimal Planning Proficiency.  _arXiv:2304.11477_ , 2023.
  * Luketina et al. (2019) Jelena Luketina, Nantas Nardelli, Gregory Farquhar, Jakob Foerster, Jacob Andreas, Edward Grefenstette, Shimon Whiteson, and Tim Rocktäschel.  A Survey of Reinforcement Learning Informed by Natural Language.  In _IJCAI_ , 2019.
  * Luo et al. (2023) Zhezheng Luo, Jiayuan Mao, Jiajun Wu, Tomás Lozano-Pérez, Joshua B Tenenbaum, and Leslie Pack Kaelbling.  Learning Rational Subgoals from Demonstrations and Instructions.  In _AAAI_ , 2023.
  * Mao et al. (2022) Jiayuan Mao, Tomas Lozano-Perez, Joshua B. Tenenbaum, and Leslie Pack Kaelbing.  PDSketch: Integrated Domain Programming, Learning, and Planning.  In _NeurIPS_ , 2022.
  * Migimatsu & Bohg (2022) Toki Migimatsu and Jeannette Bohg.  Grounding predicates through actions, 2022.
  * Misra et al. (2017) Dipendra Misra, John Langford, and Yoav Artzi.  Mapping Instructions and Visual Observations to Actions with Reinforcement Learning.  In _EMNLP_ , 2017.
  * Mu et al. (2023) Yao Mu, Qinglong Zhang, Mengkang Hu, Wenhai Wang, Mingyu Ding, Jun Jin, Bin Wang, Jifeng Dai, Yu Qiao, and Ping Luo.  EmbodiedGPT: Vision-Language Pre-training via Embodied Chain of Thought.  _arXiv:2305.15021_ , 2023.
  * Nair et al. (2022) Suraj Nair, Eric Mitchell, Kevin Chen, Silvio Savarese, and Chelsea Finn.  Learning Language-Conditioned Robot Behavior from Offline Data and Crowd-Sourced Annotation.  In _CoRL_ , 2022.
  * Nejati et al. (2006) Negin Nejati, Pat Langley, and Tolga Konik.  Learning Hierarchical Task Networks by Observation.  In _ICML_ , 2006.
  * Nottingham et al. (2023) Kolby Nottingham, Prithviraj Ammanabrolu, Alane Suhr, Yejin Choi, Hannaneh Hajishirzi, Sameer Singh, and Roy Fox.  Do embodied agents dream of pixelated sheep?: Embodied decision making using language guided world modelling.  _arXiv preprint arXiv:2301.12050_ , 2023.
  * Sharma et al. (2022) Pratyusha Sharma, Antonio Torralba, and Jacob Andreas.  Skill Induction and Planning with Latent Language.  In _ACL_ , 2022.
  * Shridhar et al. (2020) Mohit Shridhar, Jesse Thomason, Daniel Gordon, Yonatan Bisk, Winson Han, Roozbeh Mottaghi, Luke Zettlemoyer, and Dieter Fox.  ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks.  In _CVPR_ , 2020.
  * Silver et al. (2021) Tom Silver, Rohan Chitnis, Joshua Tenenbaum, Leslie Pack Kaelbling, and Tomás Lozano-Pérez.  Learning Symbolic Operators for Task and Motion Planning.  In _IROS_ , 2021.
  * Silver et al. (2022) Tom Silver, Varun Hariprasad, Reece S Shuttleworth, Nishanth Kumar, Tomás Lozano-Pérez, and Leslie Pack Kaelbling.  PDDL Planning with Pretrained Large Language Models.  In _NeurIPS Foundation Models for Decision Making Workshop_ , 2022.
  * Silver et al. (2023) Tom Silver, Soham Dan, Kavitha Srinivas, Joshua B Tenenbaum, Leslie Pack Kaelbling, and Michael Katz.  Generalized Planning in PDDL Domains with Pretrained Large Language Models.  _arXiv:2305.11014_ , 2023.
  * Song et al. (2023) Chan Hee Song, Jiaman Wu, Clayton Washington, Brian M Sadler, Wei-Lun Chao, and Yu Su.  LLM-Planner: Few-Shot Grounded Planning for Embodied Agents with Large Language Models.  In _ICCV_ , 2023.
  * Sutton et al. (1999) Richard S Sutton, Doina Precup, and Satinder Singh.  Between MDPs and Semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning.  _Artif. Intell._ , 112(1-2):181–211, 1999.
  * Tellex et al. (2011) Stefanie Tellex, Thomas Kollar, Steven Dickerson, Matthew Walter, Ashis Banerjee, Seth Teller, and Nicholas Roy.  Understanding Natural Language Commands for Robotic Navigation and Mobile Manipulation.  In _AAAI_ , 2011.
  * Tellex et al. (2020) Stefanie Tellex, Nakul Gopalan, Hadas Kress-Gazit, and Cynthia Matuszek.  Robots That Use Language.  _Annual Review of Control, Robotics, & Autonomous Systems_, 3:25–55, 2020.
  * Valmeekam et al. (2022) Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati.  Large Language Models Still Can’t Plan (A Benchmark for LLMs on Planning and Reasoning about Change).  In _NeurIPS Foundation Models for Decision Making Workshop_ , 2022.
  * Wang et al. (2023a) Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar.  Voyager: An Open-Ended Embodied Agent with Large Language Models.  _arXiv:2305.16291_ , 2023a.
  * Wang et al. (2023b) Zihao Wang, Shaofei Cai, Guanzhou Chen, Anji Liu, Xiaojian Ma, and Yitao Liang.  Describe, explain, plan and select: Interactive planning with large language models enables open-world multi-task agents, 2023b.
  * Wong et al. (2021) Catherine Wong, Kevin M Ellis, Joshua Tenenbaum, and Jacob Andreas.  Leveraging Language to Learn Program Abstractions and Search Heuristics.  In _ICML_ , 2021.
  * Xie et al. (2023) Yaqi Xie, Chen Yu, Tongyao Zhu, Jinbin Bai, Ze Gong, and Harold Soh.  Translating Natural Language to Planning Goals with Large-Language Models.  _arXiv:2302.05128_ , 2023.
  * Zhu et al. (2023) Xizhou Zhu, Yuntao Chen, Hao Tian, Chenxin Tao, Weijie Su, Chenyu Yang, Gao Huang, Bin Li, Lewei Lu, Xiaogang Wang, Yu Qiao, Zhaoxiang Zhang, and Jifeng Dai.  Ghost in the minecraft: Generally capable agents for open-world environments via large language models with text-based knowledge and memory, 2023.

##  Appendix A Appendix

We will release a complete code repository containing our full algorithm
implementation, all baselines, and benchmark tasks. Here, we provide
additional details on our implementational choices.

###  A.1 Additional Methods Implementation Details

####  A.1.1 LLM Prompting

We use gpt-3.5-turbo-16k for all experiments and baselines. Here, we describe
the contents of the LLM few-shot prompts used in our method in more detail.
Symbolic Task Decomposition For all unsolved tasks, at each iteration, we
sample a set of symbolic task descriptions as a sequence of named high-level
actions and their arguments. We construct a few-shot prompt consisting of the
following components:

  1. 1.

A brief natural language header (;;;; Given natural language goals, predict a
sequence of PDDL actions);

  2. 2.

A sequence of example ($l_{t}$, $P_{A}$) tuples containing linguistic goals
and example task decompositions. To avoid biasing the language model in
advance, we provide example task decompositions for similar, constructed tasks
that do not use any of the skills that need to be learned in our two domains.

For example, on ALFRED, these example task decompositions are for example
tasks (bake a potato and put it in the fridge, place a baked, grated apple on
top of the dining table,  place a plate in a full sink., and pick up a laptop
and then carry it over to the desk lamp, then restart the desk lamp.), and our
example task decompositions suggest named operators BakeObject, GrateObject,
FillObject, and RestartObject, none of which appear in the actual training
set.

  3. 3.

At iterations $>0$, we also provide a sequence of sampled ($l_{t}$, $P_{A}$)
tuples randomly sampled from any solved tasks and their discovered high-level
plans. This means that few-shot prompting better represents the true task
distribution over successive iterations.

In our experiments, we prompt with temperature=1.0 and draw n=4 task
decomposition samples per unsolved task.

Symbolic Operator Definition For all unsolved tasks, at each iteration, we
sample proposed operator definitions consisting of
$\textit{args},\textit{pre},\textit{eff}$ conditioned on all undefined
operator names that appear in the proposed task decompositions.

For each operator name, we construct a few-shot prompt consisting of the
following components:

  1. 1.

A brief natural language header (You are a software engineer who will be
writing planning operators in the PDDL planning language. These operators are
based on the following PDDL domain definition.

  2. 2.

The full set of environment predicates vocabulary of high-level environment
predicates ${\mathcal{P}}$, as well as valid named argument values (eg. object
types).

  3. 3.

A sequence of example $\textit{name},\textit{args},\textit{pre},\textit{eff}$
operator definitions demonstrating the PDDL definition format. As with task
decomposition, of course, we do not provide any example operator definitions
that we wish to learn from our dataset.

  4. 4.

At iterations $>0$, we include as many possible validated
$\textit{name},\textit{args},\textit{pre},\textit{eff}$ operators defined in
the current library (including new learned operators). If there are shared
patterns between operators, this means that few-shot prompting also better
represents the true operator structure over successive iterations.

In our experiments, we prompt with temperature=1.0 and draw n=3 task
decomposition samples per unsolved task. However, in our pilot experiments, we
actually find that sampling directly from the token probabilities defined by
this few-shot prompt does not produce sufficiently diverse definitions for
each operator name. We instead directly prompt the LLM to produce up to N
distinct operator definitions sequentially.

We find that GPT 3.5 frequently produces syntactically invalid operator
proposals – proposed operators often include invent predicates and object
types that are not defined in the environment vocabulary, do not obey the
predicate typing rules, or do not have the correct number and types of
arguments. While this might improve with finetuned or larger LLMs, we instead
implement a simple post-processing heuristic to correct operators with
syntactic errors, or reject operators altogether: as operator pre and
postconditions are represented as conjunctions of predicates, we remove any
invalid predicates (predicates that are invented or that specify invalid
arguments); we collect all arguments named across the predicates and use the
ground truth typing to produce the final args, and we reject any operators
that have 0 valid postcondition predicates. This post-processing procedure
frequently leaves operators underspecified (e.g., the resulting operators now
are missing necessary preconditions, which were partially generated but
syntactically incorrect in the proposal); we allow our full operator learning
algorithm to verify and reject these operators.

Symbolic Goal Proposal Finally, as described in 3.2, we also use an LLM to
propose a set of candidate goal definitions as FOL formulas $F_{t}^{\prime}$
defined over the environment predicates ${\mathcal{P}}$ for each task. Our
prompting technique is very similar to that used in the rest of our algorithm.
For each task, we we construct a few-shot prompt consisting of the following
components:

  1. 1.

A brief natural language header (You are a software engineer who will be
writing goal definitions for a robot in the PDDL planning language.

  2. 2.

The full set of environment predicates vocabulary of high-level environment
predicates ${\mathcal{P}}$, as well as valid named argument values (eg. object
types).

  3. 3.

A sequence of example $l_{t},f_{t}$ language and FOL goal formulas. In our
experiments, during training, unlike in the previous prompts (where including
ground truth operators would solve the learning problem), we do sample an
initial set of goal definitions from the training distribution as our initial
example supervision. We set supervision to a randomly sampled fraction (0.1)
of the training distribution.

  4. 4.

At iterations $>0$, we also include $l_{t},f_{t}$ examples from successfully
solved tasks.

In our experiments, we prompt with temperature=1.0 and draw n=4 task
decomposition samples per unsolved task. As with the operator proposal, we
also find that sampling directly from the token probabilities defined by this
few-shot prompt does not produce sufficiently diverse definitions for each
linguistic goal to correct for ambiguity in the human language (eg. to define
the multiple concrete Table types that a person might mean when referring to a
table). We therefore again instead directly prompt the LLM to produce up to N
distinct operator definitions sequentially.

We also post-process proposed goals using the same syntactic criterion to
remove invalid predicates in the FOL formula, and reject any empty goals.

Mini Minecraft | LLM Predicts? | Library? | Mining | Crafting | Compositional
---|---|---|---|---|---
Code Policy Prediction | Sub-policies | ✓ | 12% | 37% | 11%
Ours | Goal+Operators | ✓ | 100% | 100% | 100%
ALFRED (n=3 replications) | LLM Predicts? | Library? | Original (Simple + Compositional Tasks)
Code Policy Prediction | Sub-policies | ✓ | 11%
Ours | Goal+Operators | ✓ | 70%

Table 2: Results with GPT-4 as the LLM backbone: On both Mini Minecraft (Top)
and ALFRED (Bottom), our algorithm recovers all required operators, which
generalize to more complex compositional tasks. Switching to GPT-4 does not
impact performance trends observed across the _Code as Policies (Voyager)_
baseline and our method.

####  A.1.2 Policy Learning and Guided Low-level Search

Concretely, we implement our policy-guided low-level action search as the
following. We maintain a dictionary $D$ that maps subgoals (a conjunction of
atoms) to a set of candidate low-level action trajectories. When planning for
a new subgoal $sg$, if $D$ contains the trajectory, we prioritize trying
candidate low-level trajectories in $D$. Otherwise, we fall back to a brute-
force breadth-first search over all possible action trajectories. To populate
$D$, during the BFS, we compute the difference in the environment state before
and after the agent executes any sampled trajectory and the corresponding
trajectory $t$ that caused the state change. Here the state difference can be
viewed as a subgoal $sg$ achieved by executing $t$. Rather than directly
adding the $(sg,t)$ as a key-value pair to $D$, we lift the trajectory and
environment state change by replacing concrete objects in $sg$ and $t$ by
variables. Note that we update $D$ with each sampled trajectory in the BFS
even if it doesn’t achieve the subgoal specified in the BFS search.

When the low-level search receives a subgoal $sg$, we again lift it by
replacing objects with variables, and try to match it with entries in $D$. If
$D$ contains multiple trajectories $t$ for a given subgoal $sg$, we track how
often a given trajectory succeeds for a subgoal and prioritize trajectories
with the most successes.

###  A.2 Experiments

Learned Operator Libraries on Minecraft The following shows the full PDDL
domain definition including the initial provided vocabulary of symbolic
environment constants and predicates, initial pick and place operators and
example operator, and all ensuing learned operators combined from the Mining
and Crafting benchmarks.

Learned Operator Libraries on ALFRED The following shows the full PDDL domain
definition including the initial provided vocabulary of symbolic environment
constants and predicates, initial pick and place operators, and all ensuing
learned operators.


# Classification of Planar Graphs Associated to the Ideal of the Numerical
Semigroup

Muhammad Ahsan Binyamin, Wajid Ali, Adnan Aslam, Hasan Mahmood  Muhammad Ahsan
Binyamin
Department of Mathematics, GC University, Faisalabad, Pakistan
<EMAIL_ADDRESS>Wajid Ali
Department of Mathematics, Department of Mathematics, GC University,
Faisalabad, Pakistan<EMAIL_ADDRESS>Adnan Aslam
Department of Natural Sciences and Humanities, University of Engineering and
Technology, Lahore (RCET) 54000, Pakistan<EMAIL_ADDRESS>Hasan
Mahmood
Department of Mathematics, GC University, Lahore, Pakistan
<EMAIL_ADDRESS>
###### Abstract.

Let $\Lambda$ be a numerical semigroup and $I\subset\Lambda$ be an ideal of
$\Lambda$. The graph $G_{I}(\Lambda)$ assigned to an ideal $I$ of $\Lambda$ is
a graph with elements of $(\Lambda\setminus I)^{*}$ as vertices and any two
vertices $x,y$ are adjacent if and only if $x+y\in I$. In this paper we give a
complete characterization (up to isomorphism ) of the graph $G_{I}(\Lambda)$
to be planar, where $I$ is an irreducible ideal of $\Lambda$. This will
finally characterize non planar graphs $G_{I}(\Lambda)$ corresponding to
irreducible ideal $I$.

###### Key words and phrases:

Numerical Semigroup, Complete Graph, Planarity.

##  1\. Introduction and Preliminaries

In the recent years, the study of algebraic structures through the properties
of graphs has become an exciting topic of research. This lead to many
interesting results and questions. There are many papers on assigning graphs
to rings, groups and semigroups see [1, 2, 3, 4, 5, 6]. Several authors [7, 8,
9, 10, 11] studied different properties of these graphs including diameter,
girth, domination, central sets and planarity. Let $\Lambda$ be a numerical
semigroup. A subset $I\subset\Lambda$ is an ideal (integral ideal) of
$\Lambda$ if $I+\Lambda\subset\Lambda$. The ideal $I$ is irreducible ideal if
it cannot be written as intersection of two or more proper ideals which
contained it properly. Throughout the paper we consider $I$ to be an
irreducible ideal of $\Lambda$. Barucci [12] proved that every irreducible
ideal $I$ of numerical semigroup $\Lambda$ can be written in the form
$\Lambda\setminus B(x)$, where $B(x)=\\{y\in\Lambda:x-y\in\Lambda\\}$, for
some $x\in\Lambda$. Binyamin et al. [13] assigned a graph to numerical
semigroup and studied some properties of this class of graphs. Recently Peng
Xu et al. [14] assigned a graph to the ideal of a numerical semigroup with
vertex set $\\{v_{i}\;:\;i\in(\Lambda\setminus I)^{*}=(\Lambda\setminus
I)-\\{0\\}\\}$ and edge set $\\{v_{i}v_{j}\iff i+j\in I\\}$. It is easy to
observe that if $I$ is an irreducible ideal of $\Lambda$, then
$V(G_{I}(\Lambda))=\\{v_{i}\;:i\in B^{*}(x)$} for some $x\in\Lambda$. For
every ideal $I$ of $\Lambda$, the graph $G_{I}(\Lambda)$ is always connected
[14]. Therefore it is natural to ask when the graph $G_{I}(\Lambda)$ is
complete? It has been proved in [14], if $I$ is an irreducible ideal of
numerical semigroup $\Lambda$, then the graph $G_{I}(\Lambda)$ is not a
complete graph whenever $|V(G_{I}(\Lambda))|\geq 3$ and the clique number
$cl(G_{I}(\Lambda))$ of $\Lambda$ is given by the formula

$cl(G_{I}(\Lambda))=\left\\{\begin{array}[]{ll}\frac{n}{2}+1,&\hbox{if $n$ is
even;}\\\ \frac{n+1}{2},&\hbox{if $n$ is odd,}\end{array}\right.$

where $n$ is the order of the graph $G_{I}(\Lambda)$. This shows that whenever
$n\geq 8$, $G_{I}(\Lambda)$ has a subgraph isomorphic to complete graph
$K_{5}$ and hence $G_{I}(\Lambda)$ is not a planar graph. The motivation of
this paper is to find all the graphs $G_{I}(\Lambda)$ that are planar. To
answer this question, It is required to give a complete characterization of
the graph $G_{I}(\Lambda)$ such that the order of $G_{I}(\Lambda)$ is either 6
or 7.

A graph $G=(V(G),E(G))$ is an ordered pair with the vertex set $V(G)$ and the
edge set $E(G)$. The cardinality of the vertex set and edge set is called the
order and size of $G$ respectively. A graph $G$ is connected if every pair of
vertices $x,y\in V(G)$ is connected by a path. A graph $G$ of order $n$ is
complete if every pair of vertices of $G$ are adjacent and is denoted by
$K_{n}$. The graph $G$ is bipartite if its vertex set $V(G)$ can be
partitioned in to two sets $V_{1}(G)$ and $V_{2}(G)$ in such a way that $xy\in
E(G)$ if and only if $x\in V_{1}(G)$ and $y\in V_{2}(G)$ or vice versa. If
$|V_{1}(G)|=|V_{2}(G)|=m$, then $G$ is called a complete bipartite graph and
is denoted by $K_{m,m}$. A planar graph is a graph that can be drawn in the
plane without crossings that is, no two edges intersect geometrically except
at a vertex to which both are incident. Two graphs $G$ and $H$ are said to be
homeomorphic if both $G$ and $H$ can be obtained by a same graph by inserting
vertices of degree $2$ into its edges. It is well known that $K_{3,3}$ and
$K_{5}$ are non-planar. In order to show that a graph is planar one can use
the famous Kuratowski’s theorem which states that: A graph is planar if and
only if it contains no subgraph homeomorphic to $K_{5}$ or $K_{3,3}$. For more
undefined terminologies related to graph theory see [15, 16, 17].

The main aim of this paper is to classify all the graphs $G_{I}(\Lambda)$ of
order 6 and order 7. This, certainly helps us to give a complete answer about
the planarity of the graph $G_{I}(\Lambda)$.

##  2\. Planar and Non-planar Graphs $G_{I}(\Lambda)$

Let $\Lambda=<A>$, where $A=\\{a_{1},a_{2},\dots,a_{n}\\}$ is the minimal
system of generators. Let $x\in\Lambda$, then

$x=u_{1}a_{1}+u_{2}a_{2}+\dots+u_{n}a_{n},$

where $u_{1},u_{2},\ldots,u_{n}$ are non negative integers. Note that
$\Lambda$ can be written as

$\Lambda=\bigcup_{p=1}^{n}L^{(p)},$

where $L^{(p)}$ denote the collection of all those elements of $\Lambda$,
which can be written as a linear combination of exactly $p$ elements of $A$
that is if $x\in L^{(p)}$ then
$x=u_{1}a_{i_{1}}+u_{2}a_{i_{2}}+\ldots+u_{p}a_{i_{p}},$ where
$a_{i_{1}},a_{i_{2}},\ldots,a_{i_{p}}\in A$ and $u_{1},u_{2},\ldots,u_{p}$ are
positive integers. By using the above notation, for each $x\in\Lambda$, we
define

$L_{x}^{(p)}=\\{\Sigma\in L^{(p)}:\Sigma=x\\}.$

######  Lemma 2.1.

With the notations defined above, we have

$B(x)\supseteq\\{v_{1}a_{i_{1}}+v_{2}a_{i_{2}}+\dots+v_{p}a_{i_{p}}:0\leq
v_{i}\leq u_{i},\quad a_{i_{1}},a_{i_{2}},\ldots,a_{i_{p}}\in A\\}$

and

$|B(x)|\geq\sum\limits_{i=1}^{p}u_{i}+\sum\limits_{1\leq i_{1}<i_{2}\leq
p}u_{i_{1}}u_{i_{2}}+\sum\limits_{1\leq i_{1}<i_{2}<i_{3}\leq
p}u_{i_{1}}u_{i_{2}}u_{i_{3}}+\ldots+u_{1}u_{2}\cdots u_{p}.$

###### Proof.

The proof of this Lemma follows from the definition of $B(x)$. ∎

The following Propositions provide us the bounds in term of $L_{x}^{(p)}$ to
compute the graph $G_{I}(\Lambda)$ of order 6 and 7.

######  Proposition 2.2.

Let $\Lambda=<A>$ be a numerical semigroup of embedding dimension $n\geq 2$.
Then $\mid G_{I}(\Lambda)\mid\neq 6$, if one of the following holds:

  1. (1)

$L^{(p)}_{x}\neq\emptyset$ for $p\geq 3$

  2. (2)

$\mid L^{(1)}_{x}\mid\geq 3$.

  3. (3)

$L^{(2)}_{x}\neq\emptyset$ and $L^{(1)}_{x}=\emptyset$.

  4. (4)

$\mid L^{(1)}_{x}\mid\geq 2$ and $\mid L^{(2)}_{x}\mid\geq 2$.

######  Proposition 2.3.

Let $\Lambda=<A>$ be a numerical semigroup of embedding dimension $n\geq 2$.
Then $\mid G_{I}(\Lambda)\mid\neq 7$, if one of the following hold:

  1. (1)

$L^{(p)}_{x}\neq\emptyset$ for $p\geq 4$.

  2. (2)

$\mid L^{(3)}_{x}\mid\geq 2$.

  3. (3)

$\mid L^{(3)}_{x}\mid=1$ and $L^{(1)}_{x}\neq\emptyset$ or
$L^{(2)}_{x}\neq\emptyset$.

  4. (4)

$\mid L^{(2)}_{x}\mid\geq 4$.

  5. (5)

$\mid L^{(2)}_{x}\mid=3$ and $L^{(1)}_{x}\neq\emptyset$.

  6. (6)

$\mid L^{(2)}_{x}\mid=2$ and $\mid L^{(1)}_{x}\mid\geq 2$.

  7. (7)

$\mid L^{(2)}_{x}\mid=1$ and $\mid L^{(1)}_{x}\mid\geq 2$.

  8. (8)

$\mid L^{(1)}_{x}\mid\geq 3$.

In the following, we give the proof of Proposition 2.2, Proposition 2.3 can be
proved in a similar way.

###### Proof.

$(1):$ If $L^{(p)}_{x}\neq\emptyset$ for $p\geq 3$ then there exist
$a_{i},a_{j},a_{k}\in A$ such that $x=u_{1}a_{i}+u_{2}a_{j}+u_{3}a_{k}$, where
$u_{1},u_{2},u_{3}\geq 1$. By Lemma 2.1,
$a_{i},a_{j},a_{k},a_{i}+a_{j},a_{i}+a_{k},a_{j}+a_{k},x$ belongs to
$B^{*}(x)$. Clearly all these elements are distinct and hence $\mid
G_{I}(\Lambda)\mid\geq 7$.

$(2):$ If $\mid L^{(1)}_{x}\mid\geq 3$ then $x=u_{1}a_{i}$, $x=u_{2}a_{j}$ and
$x=u_{3}a_{k}$, where $u_{1},u_{2},u_{3}\geq 2$. Assume that
$a_{i}<a_{j}<a_{k}$, then $u_{1}>u_{2}>u_{3}$. It follows that $u_{1}\geq 5$.
By Lemma 2.1, $B^{*}(x)$ contains
$a_{i},2a_{i},3a_{i},4a_{i},5a_{i},a_{j},a_{k}$ and therefore $\mid
G_{I}(\Lambda)\mid\geq 7$.

$(3):$ If $\mid L^{(2)}_{x}\mid=1$ then $x=u_{1}a_{i}+v_{1}a_{j}$, where
$u_{1},v_{1}\geq 1$. If $u_{1}=v_{1}=1$ then $x=a_{i}+a_{j}$ and Lemma 2.1
gives $B^{*}(x)=\\{a_{i},a_{j},a_{i}+a_{j}\\}$. For $u_{1}=1$ and $v_{1}=2$,
we have $x=a_{i}+2a_{j}$ and
$B^{*}(x)=\\{a_{i},a_{j},2a_{j},a_{i}+a_{j},a_{i}+2a_{j}\\}$. Similarly, for
$u_{1}=2$ and $v_{1}=1$ we get
$B^{*}(x)=\\{a_{i},a_{j},2a_{i},a_{i}+a_{j},2a_{i}+a_{j}\\}$. Now if $u_{1}=1$
and $v_{1}\geq 3$ then
$a_{i},a_{j},2a_{j},3a_{j},a_{i}+a_{j},a_{i}+2a_{j},a_{i}+3a_{j}$ are distinct
elements of $B^{*}(x)$. Similarly, for $u_{1}\geq 3$ and $v_{1}=1$ we get
$a_{j},a_{i},2a_{i},3a_{i},a_{i}+a_{j},2a_{i}+a_{j},3a_{i}+a_{j}\in B^{*}(x)$.
If $u_{1},v_{1}\geq 2$ then note that
$a_{i},a_{j},2a_{i},2a_{j},a_{i}+2a_{j},2a_{i}+a_{j},a_{i}+a_{j},2a_{i}+2a_{j}$
are all distinct elements of $B^{*}(x)$. Hence, in all cases, we obtain $\mid
G_{I}(\Lambda)\mid\neq 6$.

Now if $\mid L^{(2)}_{x}\mid=2$ then $x=u_{1}a_{i}+v_{1}a_{j}$ and
$x=u_{2}a_{k}+v_{2}a_{l}$, where $u_{1},v_{1},u_{2},v_{2}\geq 1$ . It follows
from the previous discussion that if $u_{1}=1$ and $v_{1}\geq 3$, $u_{1}\geq
3$ and $v_{1}=1$, $u_{1},v_{1}\geq 2$, $u_{2}=1$ and $v_{2}\geq 3$, $u_{2}\geq
3$ and $v_{2}=1$, $u_{2},v_{2}\geq 2$ then $\mid G_{I}(\Lambda)\mid\geq 7$. If
$a_{i},a_{j},a_{k}$ and $a_{l}$ are not distinct then one can easily check
that the remaining possibilities does not holds. Now consider
$a_{i},a_{j},a_{k}$ and $a_{l}$ are distinct. If $u_{1}=v_{1}=1$ and
$u_{2}=v_{2}=1$ then $x=a_{i}+a_{j}=a_{k}+a_{l}$ and
$B^{*}(x)=\\{a_{i},a_{j},a_{k},a_{l},a_{i}+a_{j}\\}$, hence $\mid
G_{I}(\Lambda)\mid<6$. Now if $u_{1}=v_{1}=1$ and $u_{2}=2$, $v_{2}=1$ then
$x=a_{i}+a_{j}=2a_{k}+a_{l}$. This gives
$a_{i},a_{j},a_{k},a_{l},a_{k}+a_{l},2a_{k},a_{i}+a_{j}$ distinct elements of
$B^{*}(x)$ and therefore $\mid G_{I}(\Lambda)\mid\geq 7$. Similarly we get
$\mid G_{I}(\Lambda)\mid\geq 7$, for all the remaining possibilities.

Finally, if $\mid L^{(2)}_{x}\mid\geq 3$ then $x=u_{1}a_{i}+v_{1}a_{j}$,
$x=u_{2}a_{k}+v_{2}a_{l}$ and $x=u_{3}a_{m}+v_{3}a_{q}$, where
$u_{1},v_{1},u_{2},v_{2},u_{3},v_{3}\geq 1$. This give
$a_{i},a_{j},a_{k},a_{l},a_{m},a_{q}$ and $a_{i}+a_{j}$ belongs to $B^{*}(x)$
and therefore $\mid G_{I}(\Lambda)\mid\geq 7$.

$(3):$ If $\mid L^{(1)}_{x}\mid\geq 2$ and $\mid L^{(2)}_{x}\mid\geq 2$, then
we can assume $x=u_{1}a_{i}+v_{1}a_{j}$, $x=u_{2}a_{k}+v_{2}a_{l}$, $x=ua_{m}$
and $x=va_{q}$, where $u_{1},v_{1},u_{2},v_{2}\geq 1$, $u,v\geq 2$. From case
$(2)$, we have $x=a_{i}+a_{j}$ and $x=a_{k}+a_{l}$ is the only possibility for
which $\mid G_{I}(\Lambda)\mid<6$. Now if $a_{m}<a_{q}$ with $u>v$, then
$x=a_{i}+a_{j}$ and $x=a_{k}+a_{l}$ gives
$a_{i},a_{j},a_{k},a_{l},a_{m},a_{q},2a_{m},a_{i}+a_{j}$ distinct elements of
$B^{*}(x)$. Hence $\mid G_{I}(\Lambda)\mid\geq 8$. ∎

In the proof of Proposition 2.2, one can observe that there are some cases,
where we have $\mid G_{I}(\Lambda)\mid<6$. Therefore it is possible to get
$\mid G_{I}(\Lambda)\mid=6$ by adding some suitable conditions. The similar is
the case for Proposition 2.3. In the next theorems, we classify all
irreducible ideals $I$ such that the graph $G_{I}(\Lambda)$ is of order $6$ or
order $7$.

######  Theorem 2.4.

Let $\Lambda=<A>$ be a numerical semigroup of embedding dimension $n\geq 2$.
If $\mid G_{I}(\Lambda)\mid=6$ then $x\in\Lambda$ is one of the following:

  1. (1)

$x=6a_{i}$.

  2. (2)

$x=4a_{i}=3a_{j}$.

  3. (3)

$x=5a_{i}=2a_{j}$.

  4. (4)

$x=4a_{i}$ and $x=a_{j}+a_{k}$.

  5. (5)

$x=4a_{i}$ and $3a_{i}=2a_{k}$.

  6. (6)

$x=2a_{i}$ and $x=2a_{k}+a_{l}$.

  7. (7)

$x=3a_{i}$, $x=2a_{j}$ and $x=a_{k}+a_{l}$.

  8. (8)

$x=2a_{i}$, $x=a_{k}+a_{l}$ and $x=a_{m}+a_{n}$.

###### Proof.

Given that $\mid G_{I}(\Lambda)\mid=6$, then from Proposition 2.2, it follows
that $x\in\Lambda$ satisfy one of the following condition:

  * •

$\mid L^{(1)}_{x}\mid=1$ and $L^{(p)}_{x}=\emptyset$, $\forall$ $p\geq 2$,

  * •

$\mid L^{(1)}_{x}\mid=2$ and $L^{(p)}_{x}=\emptyset$, $\forall$ $p\geq 2$,

  * •

$\mid L^{(1)}_{x}\mid=1$, $\mid L^{(2)}_{x}\mid=1$ and
$L^{(p)}_{x}=\emptyset$, $\forall$ $p\geq 3$,

  * •

$\mid L^{(1)}_{x}\mid=2$, $\mid L^{(2)}_{x}\mid=1$ and
$L^{(p)}_{x}=\emptyset$, $\forall$ $p\geq 3$,

  * •

$\mid L^{(1)}_{x}\mid=1$, $\mid L^{(2)}_{x}\mid=2$ and
$L^{(p)}_{x}=\emptyset$, $\forall$ $p\geq 3$.

$\mathbf{Case-1:}$ If $\mid L^{(1)}_{x}\mid=1$ and $L^{(p)}_{x}=\emptyset$,
$\forall$ $p\geq 2$ then $x=la_{i}$, where $l\geq 1$. By Lemma 2.1, we get
$B^{*}(x)=\\{a_{i},2a_{i},\dots,la_{i}\\}$. As $\mid G_{I}(\Lambda)\mid=6$, it
follows that $l=6$.

$\mathbf{Case-2:}$ if $\mid L^{(1)}_{x}\mid=2$ and $L^{(p)}_{x}=\emptyset$,
$\forall$ $p\geq 2$ then $x=ua_{i}$ and $x=va_{j}$, where $a_{i}<a_{j}$,
$1<v<u$ and $u$ is not a multiple of $v$. Then it follows from Lemma 2.1, we
have $B^{*}(x)=\\{a_{i},2a_{i},\dots,ua_{i},a_{j},2a_{j}\dots,(v-1)a_{j}\\}$.
Let $pa_{i}=qa_{j}$ for some $q<p<u$ with $q=2,3,\dots,v-1$. Then
$pa_{i}+(u-p)a_{i}=ua_{i}$ and we get $qa_{j}+(u-p)a_{i}=x.$ This give
$L^{(2)}_{x}\neq\emptyset$, a contradiction. Therefore
$a_{i},2a_{i},\dots,ua_{i},a_{j},2a_{j}\dots,(v-1)a_{j}$ are distinct elements
of $B^{*}(x)$. As $\mid G_{I}(\Lambda)\mid=6$, therefore either $u=4$ and
$v=3$ or $u=5$ and $v=2$. This gives the case $(2)$ and case $(3)$.

$\mathbf{Case-3:}$ Let $\mid L^{(1)}_{x}\mid=1=\mid L^{(2)}_{x}\mid$, then
$x=ra_{i}$ and $x=ua_{k}+va_{l}$, where $r\geq 2$ and $u,v\geq 1$. By
Proposition 2.2$(2)$, we have $x=a_{k}+a_{l}$ or $x=2a_{k}+a_{l}$ or
$x=a_{k}+2a_{l}$. If $x=a_{k}+a_{l}$ and $x=ra_{i}$, it is easy to observe
that $a_{i},a_{k},a_{l}$ are distinct elements of $A$ and
$B^{*}(x)=\\{a_{k},a_{l},a_{i},2a_{i},\dots,(r-1)a_{i},x\\}$. then $\mid
B^{*}(x)\mid=6$ gives $r=4$ and we get the case $(4)$.

Now if $x=2a_{k}+a_{l}$ and $x=ra_{i}$ then
$B^{*}(x)=\\{a_{k},a_{l},2a_{k},a_{k}+a_{l},a_{i},2a_{i},\dots,$
$x=ra_{i}\\}$. Note that $a_{i}=a_{k}$ is not possible, otherwise we get
$a_{l}$ is a multiple of $a_{i}$. If $a_{i}=a_{l}$ then $a_{i}<a_{k}$,
otherwise we get either $a_{i}=2a_{k}$ or $2a_{i}=2a_{k}$. These both
conditions are not possible. Now $a_{i}<a_{k}$ gives $r>3$. $\mid
B^{*}(x)\mid=6$ gives $r=4$. Hence we get $x=4a_{i}$ and $3a_{i}=2a_{k}$ which
is the case $(5)$. Now if $a_{i},a_{k},a_{l}$ are distinct then $\mid
B^{*}(x)\mid=r+4$. As $\mid B^{*}(x)\mid=6$ therefore $r=2$ and we get the
case $(6)$. Also if $x=a_{k}+2a_{l}$ and $x=ra_{i}$ then again we get the
cases $(5)$ and $(6)$.

$\mathbf{Case-4:}$ If $\mid L^{(1)}_{x}\mid=2$ and $\mid L^{(2)}_{x}\mid=1$,
then $x=ra_{i}$, $x=sa_{j}$ and $x=ua_{k}+va_{l}$, where $r,s\geq 2$ and
$u,v\geq 1$. Assume that $a_{i}<a_{j}$ then $1<s<r$ and $r$ is not a multiple
of $s$. By Proposition 2.2(2), we have $x=a_{k}+a_{l}$ or $x=2a_{k}+a_{l}$ or
$x=a_{k}+2a_{l}$. For $u=2$ and $v=1$, we get
$B^{*}(x)=\\{a_{k},a_{l},2a_{k},a_{k}+a_{l},a_{j},2a_{j},\dots,(s-1)a_{j},a_{i},2a_{i},\dots,ra_{i}\\}$.
Similarly, for $u=1$ and $v=2$ we get
$B^{*}(x)=\\{a_{k},a_{l},2a_{l},a_{k}+a_{l},a_{j},2a_{j},\dots,(s-1)a_{j},a_{i},2a_{i},\dots,ra_{i}\\}$.
Note that $a_{i}$ or $a_{j}$ can not be equal to $a_{k}$, otherwise we get
$a_{l}$ is a multiple of $a_{i}$ or $a_{j}$. Now if $a_{i}=a_{l}$ or
$a_{j}=a_{l}$ then $\mid B^{*}(x)\mid=r+s+2$ and if $a_{i},a_{j},a_{k},a_{l}$
are different then $\mid B^{*}(x)\mid=r+s+3$, as $1<s<r$ therefore $\mid
B^{*}(x)\mid>6$. Now if $u=1,v=1$ then $a_{i},a_{j},a_{k},a_{l}$ are different
and
$B^{*}(x)=\\{a_{k},a_{l},a_{j},2a_{j},\dots,(s-1)a_{j},a_{i},2a_{i},\dots,ra_{i}\\}$.
This gives $\mid B^{*}(x)\mid=r+s+1$. $\mid B^{*}(x)\mid=6$ gives $r=3$ and
$s=2$ which is the case $(7)$.

$\mathbf{Case-5:}$ If $\mid L^{(1)}_{x}\mid=1$ and $\mid L^{(2)}_{x}\mid=2$,
then $x=u_{1}a_{k}+v_{1}a_{l}$, $x=u_{2}a_{m}+v_{2}a_{n}$ and $x=ra_{i}$,
where $r\geq 2$ and $u_{1},u_{2},v_{1},v_{2}\geq 1$. By Proposition 2.2(2), we
have $x=a_{k}+a_{l}$ and $x=a_{m}+a_{n}$. In this case we have
$B^{*}(x)=\\{a_{k},a_{l},a_{m},a_{n},a_{i},2a_{i},\dots,ra_{i}\\}$. Since
$a_{k},a_{l},a_{m},a_{n},a_{i}$ are distinct, it follows that $\mid
B^{*}(x)\mid=r+4$. $\mid B^{*}(x)\mid=6$ gives $r=2$ which is the case $(8)$.
∎

######  Theorem 2.5.

Let $\Lambda=<A>$ be a numerical semigroup of embedding dimension $n\geq 2$.
If $\mid G_{I}(\Lambda)\mid=7$ then $x\in\Lambda$ satisfy one of the
following:

  1. (1)

$x=7a_{i}$.

  2. (2)

$x=5a_{i}=3a_{j}$.

  3. (3)

$x=3a_{i}+a_{j}$ or $x=a_{i}+3a_{j}$.

  4. (4)

$x=5a_{i}$ and $x=a_{j}+a_{k}$.

  5. (5)

$x=3a_{i}$ and $x=2a_{j}+a_{k}$ or $x=a_{j}+2a_{k}$.

  6. (6)

$x=a_{i}+a_{j}$ and $x=2a_{k}+a_{l}$.

  7. (7)

$x=3a_{i}$ and $x=a_{k}+a_{l}$ and $x=a_{m}+a_{n}$.

  8. (8)

$x=a_{i}+a_{j}$ and $x=a_{k}+a_{l}$ and $x=a_{m}+a_{n}$.

  9. (9)

$x=a_{i}+a_{j}+a_{k}$.

###### Proof.

Given that $\mid G_{I}(\Lambda)\mid=7$, then from Proposition 2.3, it follows
that $x$ satisfy one of the following condition:

  * •

$\mid L^{(1)}_{x}\mid=1$ and $L^{(p)}_{x}=\emptyset$, $\forall$ $p\geq 2$,

  * •

$\mid L^{(1)}_{x}\mid=2$ and $L^{(p)}_{x}=\emptyset$, $\forall$ $p\geq 2$,

  * •

$L^{(1)}_{x}=\emptyset,$, $\mid L^{(2)}_{x}\mid=1$, $L^{(p)}_{x}=\emptyset,$
$\forall$ $p\geq 3$,

  * •

$\mid L^{(1)}_{x}\mid=1$, $\mid L^{(2)}_{x}\mid=1$, $L^{(p)}_{x}=\emptyset$,
$\forall$ $p\geq 3$,

  * •

$\mid L^{(1)}_{x}\mid=1$, $\mid L^{(2)}_{x}\mid=1$, $L^{(p)}_{x}=\emptyset$,
$\forall$ $p\geq 3$,

  * •

$L^{(1)}_{x}=\emptyset,$, $\mid L^{(2)}_{x}\mid=2$, $L^{(p)}_{x}=\emptyset$,
$\forall$ $p\geq 3$,

  * •

$\mid L^{(1)}_{x}\mid=1$, $\mid L^{(2)}_{x}\mid=2$, $L^{(p)}_{x}=\emptyset$,
$\forall$ $p\geq 3$,

  * •

$L^{(1)}_{x}=\emptyset$, $\mid L^{(2)}_{x}\mid=3$, $L^{(p)}_{x}=\emptyset$,
$\forall$ $p\geq 3$,

  * •

$\mid L^{(3)}_{x}\mid=1$, $L^{(p)}_{x}=\emptyset$, $\forall$ $p\neq 3$ and
$x=a_{i}+a_{j}+a_{k}$.

These possibilities can be checked in a similar way as we did in Theorem 2.4
to get the required result. ∎

Theorem 2.4 and Theorem 2.5 give us all irreducible ideals $I$ such that
$G_{I}(\Lambda)$ is of order 6 or order 7. This is easy to see that there are
some cases where we get the graphs $G_{I}(\Lambda)$ which are isomorphic to
each other. Our next propositions classify all graphs $G_{I}(\Lambda)$ upto
isomorphism of order 6 and order 7.

######  Corollary 2.6.

A graph $G_{I}(\Lambda)$ of order $6$ is isomorphic to one of the graphs given
in the Table $1$:

Type | Degree sequence | Graph
---|---|---
$1$ | $(1,2,3,3,4,5)$ |
$2$ | $(2,3,3,4,5,5)$ |
$3$ | $(2,3,4,4,4,5)$ |
$4$ | $(3,3,4,4,5,5)$ |
$5$ | $(3,4,4,4,4,5)$ |
$6$ | $(4,4,4,4,5,5)$ |
Table 1.

###### Proof.

This is an easy consequence of Theorem 2.4. ∎

######  Corollary 2.7.

A graph $G_{I}(\Lambda)$ of order $7$ is isomorphic to one of the graphs given
in the Table $2$:

Type | Degree sequence | Graph
---|---|---
$1$ | $(1,2,3,3,4,5,6)$ |
$2$ | $(2,3,3,4,5,5,6)$ |
$3$ | $(3,3,3,5,5,5,6)$ |
$4$ | $(3,4,4,5,5,5,6)$ |
$5$ | $(4,4,5,5,5,5,6)$ |
$6$ | $(5,5,5,5,5,5,6)$ |
Table 2.

###### Proof.

This is an easy consequence of Theorem 2.5. ∎

######  Theorem 2.8.

Let $\Lambda$ be a numerical semigroup of embedding dimension $n\geq 2$. Then
$G_{I}(\Lambda)$ is planar if one of the following hold:

  1. (1)

$\mid G_{I}(\Lambda)\mid\leq 5$.

  2. (2)

$\mid G_{I}(\Lambda)\mid=6$ and $G_{I}(\Lambda)$ is of type $1,2,3$ or $4$.

  3. (3)

$\mid G_{I}(\Lambda)\mid=7$ and $G_{I}(\Lambda)$ is of type $1,2$ or $3$.

###### Proof.

$(1)$ is trivial.
$(2)$ If $\mid G_{I}(\Lambda)\mid=6$ and $G_{I}(\Lambda)$ is of type $1,2$ or
$3$ then $G_{I}(\Lambda)$ is trivially planar. Now if $G_{I}(\Lambda)$ is of
type $4$ then
$B^{*}(x)=\\{a_{i},a_{j},a_{k},a_{j}+a_{k},2a_{j},2a_{i}+a_{j},x\\}$ with
deg$(v_{a_{i}})=5$, deg$(v_{a_{j}})=3$, deg$(v_{a_{k}})=3$,
deg$(v_{a_{j}+a_{k}})=4$, deg$(v_{2a_{j}})=4$, and deg$(v_{x})=5$.
Since $\mid G_{I}(\Lambda)\mid=6$, therefore $cl(G_{I}(\Lambda))=4$. This
shows that $G_{I}(\Lambda)$ cannot have a subgraph which is isomorphic to
complete graph $K_{5}$. Now consider a subgraph $H$ of $G_{I}(\Lambda)$ such
that $\mid H\mid=6$ and the degree sequence of $H$ is $(3,3,3,3,3,3)$. This
give $V(H)=V(G_{I}(\Lambda))$ and
$E(H)=E(G_{I}(\Lambda))-\\{v_{a_{i}}v_{x},v_{a_{i}}v_{2a_{j}},v_{a_{j}+a_{k}}v_{x}\\}$
or $V(H)=V(G_{I}(\Lambda))$ and
$E(H)=E(G_{I}(\Lambda))-\\{v_{a_{i}}v_{x},v_{a_{i}}v_{a_{j}+a_{k}},v_{2a_{j}}v_{x}\\}$.
In both cases, one can easily see that $H\ncong K_{3,3}$.
$(3)$ can be proved in a similar way as we proved $(2)$. ∎

######  Theorem 2.9.

Let $\Lambda$ be a numerical semigroup of embedding dimension $n\geq 2$. Then
$G_{I}(\Lambda)$ is non-planar if one of the following hold:

  1. (1)

$\mid G_{I}(\Lambda)\mid\geq 8$,

  2. (2)

$\mid G_{I}(\Lambda)\mid=6$ and $G_{I}(\Lambda)$ is of type $5$ or $6$.

  3. (3)

$\mid G_{I}(\Lambda)\mid=7$ and $G_{I}(\Lambda)$ is of type $4,5$ or $6$.

###### Proof.

$\mathbf{(1):}$ If $\mid G_{I}(\Lambda)\mid\geq 8$ then
$cl(G_{I}(\Lambda))\geq 5$ and therefore $G_{I}(\Lambda)$ must has a subgraph
isomorphic to complete graph $K_{5}$.
$\mathbf{(2):}$ Assume that $\mid G_{I}(\Lambda)\mid=6$ and $G_{I}(\Lambda)$
is of type $5$ then $B^{*}(x)=\\{a_{i},a_{j},2a_{i},2a_{j},$
$3a_{i},4a_{i}\\}$ with deg$(v_{a_{i}})=3$, deg$(v_{a_{j}})=4$,
deg$(v_{2a_{i}})=4$, deg$(v_{2a_{j}})=4$, deg$(v_{3a_{i}})=4$ and
deg$(v_{4a_{i}})=5$. Since $\mid G_{I}(\Lambda)\mid=6$, therefore
$cl(G_{I}(\Lambda))=4$. This shows that $G_{I}(\Lambda)$ cannot have a
subgraph which is isomorphic to complete graph $K_{5}$. Consider a subgraph
$H$ of $G_{I}(\Lambda)$ such that $V(H)=V(G_{I}(\Lambda))$ and
$E(H)=E(G_{I}(\Lambda))-\\{v_{a_{j}}v_{4a_{i}},v_{2a_{i}}v_{3a_{i}},v_{2a_{j}}v_{4a_{i}}\\}$.
Note that we can partition the set of vertices of $H$ into
$V_{1}=\\{a_{i},2a_{i},3a_{i}\\}$ and $V_{2}=\\{a_{j},2a_{j},4a_{i}\\}$ such
that no edge has both endpoints in the same subset and every possible edge
that could connect vertices in different subsets is part of the graph. This
implies $H$ is isomorphic to complete bipartite graph $K_{3,3}$ and therefore
$G_{I}(\Lambda)$ is non-planar.
Remaining cases of $\mathbf{(2)}$ and $\mathbf{(3)}$ can be proved in a
similar way.

$v_{a_{i}}$$v_{4a_{i}}$$v_{2a_{j}}$$v_{3a_{i}}$$v_{a_{j}}$$v_{2a_{i}}$Fig-1
$v_{a_{i}}$$v_{2a_{i}}$$v_{3a_{i}}$$v_{a_{j}}$$v_{2a_{j}}$$v_{4a_{i}}$Fig-2

∎

##  3\. Conclusion

In this article, we have given a complete answer about the planarity of the
graph $G_{I}(\Lambda)$ associated with the irreducible ideal of a numerical
semigroup. However, for any integral ideal $I$, this is an open question.

Conflict of Interests: The authors hereby declare that there is no conflict of
interests regarding the publication of this paper.

Data Availability Statement: No data is required for this study.

Funding Statement: This research is carried out as a part of the employment of
the authors.

## References

  * [1] Afkhami, M. and Khashyarmanesh, K., The intersection graph of ideals of a lattice, Note Mat. 34(2) (2014), 135-143.
  * [2] D.F. Anderson, P.S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra 217 (1999) 434–447.
  * [3] Anderson, D. D. and Badawi, A., The total graph of a commutative ring, J. Algebra 320 (2008), 2706-2719.
  * [4] A. Badawi, On the annihilator graph of a commutative ring, Comm. Algebra 42 (2014) 108–121. http://dx.doi.org/10.1080/00927872.2012.707262.
  * [5] M. Behboodi, Z. Rakeei, The annihilating-ideal graph of commutative rings I, J. Algebra Appl. 10 (4) (2011) 727–739.
  * [6] H.R. Maimani, M. Salimi, A. Sattari, S. Yassemi, Comaximal graph of commutative rings, J. Algebra 319 (2008) 1801–1808.
  * [7] D.F. Anderson, S.B. Mulay, On the diameter and girth of a zero-divisor graph, J. Pure Appl. Algebra 210 (2007) 543-550.
  * [8] T. Tamizh Chelvam, K. Selvakumar, Central sets in annihilating-ideal graph of a commutative ring, J. Combin. Math. Combin. Comput. 88 (2014) 277–288.
  * [9] T. Tamizh Chelvam, K. Selvakumar, Domination in the directed zero-divisor graph of ring of matrices, J. Combin. Math. Combin. Comput. 91 (2014) 155–163.
  * [10] S. Akbari, H.R. Maimani, S. Yassemi, When a zero-divisor graph is planar or a complete r-partite graph, J. Algebra 270 (2003) 169-180.
  * [11] Beck, I., Coloring of commutative rings, J. Algebra 116 (1998), 208-226.
  * [12] Barucci, V., Decompositions of ideals into irreducible ideals in numerical semigroups. Journal of Commutative Algebra, 2(3) (2010), 281-294.
  * [13] Binyamin, M. A., Siddiqui, H. M. A., Khan, N. M., Aslam, A., Rao, Y., Characterization of graphs associated with numerical semigroups. Mathematics, 7, 557 (2019), doi:10.3390/math7060557.
  * [14] P. Xu, M. A. Binyamin, A. Aslam, W. Ali, H. Mahmood and Hao Zhou, Characterization of Graphs Associated to the Ideal of the Numerical Semigroups, Journal of Mathematics, Volume 2020, Article ID 6094372, 6 pages.
  * [15] Chartrand, G., Introduction to graph theory. Tata McGraw-Hill Education (2006).
  * [16] Diestel, R., Graph Theory, New York: Springer-Verlag (1997).
  * [17] West, D. B., Introduction to graph theory (Vol. 2). Upper Saddle River: Prentice hall (2001).