11institutetext: University of South Carolina, USA 22institutetext: IIIT-
Delhi, India
22email<EMAIL_ADDRESS>22email<EMAIL_ADDRESS>22email:
<EMAIL_ADDRESS>22email<EMAIL_ADDRESS>22email:
<EMAIL_ADDRESS>22email<EMAIL_ADDRESS>
# A Planning Ontology to Represent and Exploit Planning Knowledge for
Performance Efficiency

Bharath Muppasani 11 Vishal Pallagani 11 Biplav Srivastava 11 Raghava
Mutharaju 22 Michael N. Huhns 11 Vignesh Narayanan 11

###### Abstract

Ontologies are known for their ability to organize rich metadata, support the
identification of novel insights via semantic queries, and promote reuse. In
this paper, we consider the problem of automated planning, where the objective
is to find a sequence of actions that will move an agent from an initial state
of the world to a desired goal state. We hypothesize that given a large number
of available planners and diverse planning domains; they carry essential
information that can be leveraged to identify suitable planners and improve
their performance for a domain. We use data on planning domains and planners
from the International Planning Competition (IPC) to construct a planning
ontology and demonstrate via experiments in two use cases that the ontology
can lead to the selection of promising planners and improving their
performance using macros - a form of action ordering constraints extracted
from planning ontology. We also make the planning ontology and associated
resources available to the community to promote further research.

Resource Type: Ontology, Knowledge Graph
Licence: Creative Commons Attribution 4.0 License
URL: https://github.com/BharathMuppasani/AI-Planning-Ontology

###### Keywords:

Ontology Automated Planning Planner Improvement.

##  1 Introduction

Automated planning, where the objective is to find a sequence of actions that
will transition an agent from the initial state of the world to a desired goal
state, is an active sub-field of Artificial Intelligence (AI). The ability to
generate plans and make decisions in complex domains, such as robotics,
logistics, and manufacturing, has led to significant progress in the
automation of planning. Currently, there are numerous planning domains,
planners, search algorithms, and associated heuristics in the field of
automated planning. Each planner, in conjunction with a search algorithm and
heuristic, generates plans with varying degrees of quality, cost, and
optimality. The empirical results available for various planning problems,
ranked by planner performance and the heuristics used as available in
International Planning Competition (IPC), can provide valuable information to
identify various tunable parameters to improve planner performance.
Traditionally, improving planner performance involves manually curating
potential combinations to identify the optimal planner configuration. However,
there has been limited effort to model the available information in a
structured knowledge representation, such as an ontology, to facilitate
efficient reasoning and enhance planner performance.

To address the challenge of representing planning problems and associated
information in a structured manner, we propose an ontology for AI planning. An
ontology formally represents concepts and their relationships [7], which
enables systematic analysis of planning domains and planners. The proposed
ontology captures the features of a domain and the capabilities of planners,
facilitating reasoning with existing planning problems, identifying
similarities, and suggesting different planner configurations. Planning
ontology can also be a useful resource for the creation of new planners as it
captures essential information about planning domains and planners, which can
be leveraged to design more efficient planning algorithms. Furthermore,
ontology can promote knowledge sharing and collaboration within the planning
community.

In the field of planning, several attempts have been made to create ontologies
to enhance the understanding of planners’ capabilities. For instance, Plan-
Taxonomy [2] introduced a taxonomy that aimed to explain the functionality of
planners. Additionally, authors in [6] present a comprehensive ontology called
PLANET, which represents plans in real-world domains and can be leveraged to
construct new applications. Nonetheless, the reusability of PLANET is limited
as it is not open-sourced. Consequently, researchers face difficulty in
extending or replicating the ontology.

This paper outlines our methodology for constructing an ontology to represent
AI planning domains, leveraging information obtained from the IPC. In our
current work, we extended our initial research [11]. Specifically, we have
enhanced the ontology to more accurately depict the various concepts within
the planning domain. Furthermore, we include additional use cases of our
ontology and provide experimental evaluations to support our findings further.
Building a planning ontology using data from IPC offers several benefits, such
as comprehensive coverage of planning domains, a rich source for various
benchmark evaluation metrics, and documentation for planners. However, the
ontology is not limited to the PDDL representation or domains in IPC and can
easily be extended to any. Our contributions are at the intersection of
ontologies and AI planning and can be summarized as follows.

  * •

Planning Ontology: We developed an ontology for AI planning that can be used
to represent and organize knowledge related to planning problems. Our ontology
provides a structured way to capture the relationships between different
planning concepts, enabling more efficient and effective knowledge sharing and
reuse.

  * •

Usecase 1: Identifying Most Promising Planner for Performance: We demonstrate
the ontology’s usage for identifying the best-performing planner for a
specific planning domain using data from IPC-2011.

  * •

Usecase 2: Macro Selection for Improving Planner Performance: We demonstrate
the usage of ontology to extract domain-specific macros - which are action
orderings and show that they can improve planner performance drastically.

In the remainder of the paper, we start with preliminaries about on automated
planning and IPC. We then give an overview of the existing literature on
ontologies for planning. Following this, we present a detailed description of
the ontology construction process and its usage. We then discuss the proposed
planning ontology and conclude with future research directions.

##  2 Preliminaries

In this section, we describe the necessary background for automated planning
and the significance of the International Planning Competition.

Figure 1: Demonstration of automated planning problem with blocksworld domain
example

###  2.1 Automated Planning

Automated planning, also known as AI planning, is the process of finding a
sequence of actions that will transform an initial state of the world into a
desired goal state [5]. It involves constructing a plan or a sequence of
actions that will achieve a specified objective while respecting any
constraints or limitations that may be present. Formally, automated planning
can be defined as a tuple $(S,A,T,I,G)$, where:

  * •

$S$ is the set of possible states of the world

  * •

$A$ is the set of possible actions that can be taken

  * •

$T$ is the transition function that describes the effects of taking an action
on the current state of the world

  * •

$I$ is the initial state of the world

  * •

$G$ is the desired goal state

Using this notation, the problem of automated planning can be framed as
finding a sequence of actions $\prec a_{1},a_{2},...,a_{k}\succ$ that will
transform the initial state $I$ into the goal state $G$, while respecting any
constraints or limitations on the actions. A problem is defined in terms of a
domain and a problem instance. The domain defines the possible actions that
can be taken and the effects of each action, while the problem instance
specifies the initial state of the world and the desired goal state. Various
techniques can be used to solve the planning problem, such as search
algorithms, constraint-based reasoning, and optimization methods. These
techniques involve exploring the space of possible plans and selecting the one
that satisfies the objective and any constraints. Figure 1 illustrates an
automated planning scenario for the blocksworld domain, where an initial state
can be transformed into a goal state by executing a sequence of actions.

Attributes modeled about a domain.

  1. 1.

Requirements: A list of requirements that the planner must satisfy in order to
solve the domain. Requirements include durative actions, conditional effects,
or negative preconditions. For example, in blocksworld domain with types
involved, one of the requirements is _typing_.

  2. 2.

Predicates: Predicates are fundamental elements in the planning domain that
define the properties of the world. They are used to describe the initial and
goal states, as well as the preconditions and effects of actions. Predicates
are usually defined as logical expressions over a set of variables, where each
variable can take on a finite number of values. In the context of planning,
predicates are typically used to represent facts about the world that can be
true or false, such as the location of an object or the status of a machine.
For example, in blocksworld domain, the predicate `(on b1 b2)` could indicate
that block ’b2’ is on top of block ’b1’.

  3. 3.

Actions: Actions are the basic units of change in the planning domain. They
represent atomic operations that can be performed to transform the world from
one state to another. Each action has a name, a set of parameters,
preconditions that must be satisfied before the action can be executed, and
effects that describe the changes that the action makes to the world. Actions
can be used to model a wide variety of operations, ranging from simple
movements or transformations to complex processes such as planning or
decision-making. For example, in blocksworld domain, the action `unstack b2
b1` can be used to unstack block ’b2’ from block ’b1’.

  4. 4.

Preconditions: Preconditions are the conditions that must be true before an
action can be executed. They are usually defined using predicates and can
involve multiple variables. Preconditions can also be negative, which means
that a certain condition must not be true for an action to be executed. In
planning, preconditions ensure that actions are only executed when the
necessary conditions have been met, such as ensuring that a machine is turned
off before it is serviced. For example, in blocksworld domain, the action
`unstack b2 b1` has a precondition of `(on b1 b2)`, meaning that for the
action to be valid, the block ’b2’ should be on top of block ’b1’.

  5. 5.

Effects: Effects describe the changes that an action makes to the world. They
are usually defined using predicates and can involve multiple variables.
Effects can be positive, which means that a certain condition becomes true
after the action is executed, or negative, which means that a certain
condition becomes false after the action is executed. In the context of
planning, effects are used to model the changes that result from executing an
action, such as moving an object from one location to another or turning a
machine on. For example, in blocksworld domain, when the action `unstack b2
b1` is executed, one of its effect is `(not (on b1 b2))`, indicating that
block ’b2’ is no longer on top of block ’b1’.

  6. 6.

Constants: Constants are values that are fixed and do not change during the
execution of the planning problem. They are used to represent objects or
entities in the world that have a fixed value, such as the speed limit on a
road. Constants can be used to simplify the planning problem by reducing the
number of variables that need to be considered and by providing a fixed set of
values that can be used in predicates and actions. For example, in blocksworld
domain, the constant _table_ could represent the surface on which the blocks
are initially placed.

  7. 7.

Types: Types are used to classify objects or entities in the world based on
their attributes or properties. They are used to define the domain of values
that a variable can take on and can be used to constrain the values that are
assigned to variables. In the context of planning, types are typically used to
group related objects or entities together, such as cars or bicycles, and to
specify the properties that are common to all members of a type, such as their
color or size. For example, in blocksworld domain with types involved, one can
represent the predicate as `(on ?x - block ?y - block)` stating that the
parameters in the predicate are of type _block_.

Attributes modeled about a problem instance from a domain.

  1. 1.

Name: The name of the planning problem.

  2. 2.

Domain: The name of the planning domain that the problem belongs to.

  3. 3.

Objects: A list of objects that are present in the planning problem. Objects
are typically defined in terms of their type and name. In the example shown in
Figure 1, objects are b1, b2, and b3.

  4. 4.

Initial State: A description of the initial state of the world, including the
values of all relevant predicates. Figure 1 represents an example initial
state.

  5. 5.

Goal State: A description of the desired goal state of the world, including
the values of all relevant predicates. Figure 1 represents an example goal
state.

Each of these attributes are essential for defining a complete planning
problem that an automated planner can solve.

###  2.2 International Planning Competition (IPC)

IPC serves as a significant means of assessing and comparing various planning
systems. By presenting new planners and benchmark problems each year, the
competitions aim to stimulate the advancement of new planning methodologies
and reflect current trends and challenges in the field. The competition
comprises multiple tracks, each covering various planning problems such as
classical, temporal, and probabilistic planning. These tracks include
benchmark problems that evaluate the performance of planners concerning
parameters such as plan quality, plan length, and run time. The results of
these competitions provide insights into the current state-of-the-art in
planning and help identify the strengths and weaknesses of different planning
systems. IPC can serve as an excellent starting point for building a planning-
related ontology as the benchmark problems used in these competitions can
provide a comprehensive overview of the domain and the types of problems that
planners need to solve.

##  3 Related Work

The use of ontology-based knowledge representation and reasoning has been
extensively studied in various domains, including automated planning. This
section focuses on the applications of ontology-based knowledge representation
and reasoning in the context of planning and related domains. In [13], an
ontology is constructed for the Joint Forces Air Component Commander (JFACC)
to represent knowledge from the air campaign domain. The ontology is
modularized to facilitate data organization and maintenance, but its
applicability is domain-specific, unlike our approach. In [15], the authors
automate the knowledge discovery workflow using ontology and AI planning,
creating a Knowledge Discovery (KD) ontology to represent the KD domain and
converting its variables to a Planning Domain Definition Language (PDDL)
format to obtain the PDDL domain. The ontology’s objects represent initial and
goal states, forming the KD task, which represents a specific problem. The
authors use the Fast-Forward (FF) planning system to generate the required
plans. In a survey of ontology-based knowledge representation and reasoning in
the planning domain, [4] suggest that knowledge reasoning approaches can draw
new conclusions in non-deterministic contexts and assist with dynamic
planning. In [6], a reusable ontology, PLANET, is proposed for representing
plans. PLANET includes representations for planning problem context, goal
specification, plan, plan task, and plan task description. However, PLANET
does not include representations for some entities commonly associated with
planning domains, such as resources and time. Our planning ontology draws
inspiration from PLANET and appends more metadata for planner improvement. In
[1], a domain-independent approach is presented that advances the state of the
art by augmenting the knowledge of a planning task with pertinent goal
opportunities. The authors demonstrate that incorporating knowledge obtained
from an ontology can aid in producing better-valued plans, highlighting the
potential for planner enhancement using more tuning parameters, which are
captured in our planning ontology. In general, these studies demonstrate the
potential of ontology-based knowledge representation and reasoning in the
planning domain, including applications such as representing plans, aiding in
air campaign planning, automating knowledge discovery workflows, and
developing context-aware planning services.

##  4 Planning Ontology

Figure 2: Planning ontology capturing different concepts of automated planning
domain, problem, plan, and planner performance separated into categories
(shown as colored rectangles)

This section covers the construction of planning ontology to capture the
essential details of automated planning. We will discuss the considerations,
challenges, benefits, and limitations of using ontologies for automated
planning, to provide a better understanding of how they can improve the
efficiency and effectiveness of automated planning systems.

###  4.1 Competency Questions

Competency questions for an ontology are focused on the needs of the users who
will be querying the ontology. These questions are designed to help users
explore and understand the concepts and relationships within the ontology, and
to find the information they need within the associated knowledge base. By
answering these questions, the ontology can be better scoped and tailored to
meet the needs of its users.

  * •

C1: What are the different types of planners used in automated planning?

  * •

C2: What is the relevance of planners in a given problem domain?

  * •

C3: What are the available actions for a given domain?

  * •

C4: What problems in a domain satisfy a given condition?

  * •

C5: What are all requirements a given domain has?

  * •

C6: What is the cost associated with generating a plan for a given problem?

  * •

C7: How many parameters does a specific action have?

  * •

C8: What planning type a specific planner belongs to?

  * •

C9: What requirements does a given planner support?

  * •

C10: What are the different `types` present in a domain?

###  4.2 Design

An ontology is a formal and explicit representation of concepts, entities, and
their relationships in a particular domain. In this case, ontology is
concerned with the domain of automated planning, which refers to the process
of generating a sequence of actions to achieve a particular goal within a
given set of constraints. The ontology aims to provide a structured framework
for organizing and integrating knowledge about this domain, which can be
useful in various applications, such as designing planning algorithms,
extracting best-performing planners given a domain, or learning domain-
specific macros.

Figure 2 shows an ontology that aims to encompass the various concepts of
automated planning separated into categories of `Domain`, `Problem`, `Plan`,
and `Planner`. The ontology for automated planning is composed of 19 distinct
classes and 25 object properties. These classes and properties are designed to
represent the various elements of the automated planning domain and its
associated problems.

####  4.2.1 Domain

The Domain category of the ontology comprises classes that represent the
general characteristics of the planning domain. These classes include the
Domain - `Requirements`, `Types`, `Predicates`, `Constraints`, and `Actions`
that can be used to solve problems in that domain. The classes in the Domain
category are designed to provide a structured framework for organizing and
integrating knowledge about the problem domain, which can be useful in various
applications such as designing planning algorithms, extracting best-performing
planners given a domain, or learning domain-specific macros.

####  4.2.2 Problem

The Problem category of the ontology includes classes that represent specific
problems within a given domain. These classes are designed to capture the
details of a particular problem, such as the `Objects` defined in the problem,
which is an instance of the ’types’ defined in the planning domain, the
`Initial State` of the problem, and the `Goal State` which are a subclass of
the parent class `State` which describes the current state of the problem
domain.

####  4.2.3 Plan

The Plan category of the ontology includes classes that represent the sequence
of actions that must be taken to solve a given problem. The `Plan` class is
used to store the knowledge about the plans that planners generate for
specific problems. The plan cost for each plan is stored as a data property
(non-negative integer) of the `Plan` class. This enables planners to be
compared based on the quality of the plans they generate, as well as the cost
of those plans.

####  4.2.4 Planner

The Planner category of the ontology includes classes that capture the details
of planner performance from previous IPCs. Specifically, `Planning Domain`
relevance to a `Planner` is classified based on the percentage of problems
they have successfully solved, which is then categorized into three levels of
relevance to the planner: low, medium, and high. By incorporating this
information into the ontology, planners can be evaluated based on their
performance in different problem domains, and more informed decisions can be
made about which planners to use for a given problem. In addition, this
information can be used to guide the development of new planners and to
evaluate their performance against established benchmarks.

###  4.3 Accessing Planning Ontology

We have taken various measures to ensure that our planning ontology follows
the FAIR principles [14] of being Findable, Accessible, Interoperable, and
Reusable. To assist users in exploring and utilizing our ontology, we have
made it accessible through a persistent URL111PURL -
https://purl.org/ai4s/ontology/planning and our GitHub
repository222https://github.com/BharathMuppasani/AI-Planning-Ontology. Our
repository contains ontology model files, mapping scripts, and utility scripts
that extract information from PDDL domains and problems into intermediary JSON
format and add the extracted data as triples using our model ontology,
creating a knowledge graph. We provide sample SPARQL queries that address the
ontology’s competency questions mentioned earlier. Moreover, our ontology
documentation, which is accessible through the GitHub repository, provides a
comprehensive overview of the ontology’s structure, concepts, and relations,
including ontology visualization. This documentation serves as a detailed
guide for users to comprehend the ontology’s applications in the automated
planning domain. We also provide the scripts and results from the ontology
evaluation, which are presented as use cases of our ontology in later
sections, in our repository, along with accompanying documentation.

##  5 Usage of Planning Ontology

In the following section, we show the evaluation of a few competency questions
and discuss two use cases of our planning ontology.

Figure 3: Knowledge graph representation for blocksworld domain from IPC-2000

####  5.0.1 Evaluation of Competency questions:

For the evaluation of the competency questions, we have considered a sample
knowledge graph, shown in Figure 3, for `blocksworld` from IPC-2000 domain
created using planning ontology shown in Figure 2. SPARQL queries for each of
these questions can be found at our GitHub Repository2.

  1. 1.

C1: What are the different types of planners used in automated planning?
Question Type: Extracting planner information.
Sufficiency Condition: There should exist at least one individual for
`Planner` class.
Result: Shown in Table 1.

S.No | Planner
---|---
1 | FF
2 | FastDownward
3 | LPG
4 | CPT4
5 | SHOP2
Table 1: Results for C1 with knowledge graph in Figure 3

  2. 2.

C2: What is the relevance of planners in ’blocksworld’ domain?
Question Type: Extracting best planner for a domain.
Sufficiency Condition: There should exist at least one `Planner` individual
having either of the relevance properties with ’blocksworld’ individual of
`PlanningDomain` class.
Result: Shown in Table 2.

S.No | Domain | Relation | Planner
---|---|---|---
1 | blocksworld | hasLowRelevancePlanner | CPT4
2 | blocksworld | hasLowRelevancePlanner | SHOP2
3 | blocksworld | hasHighRelevancePlanner | FF
4 | blocksworld | hasHighRelevancePlanner | FastDownward
5 | blocksworld | hasMediumRelevancePlanner | LPG
Table 2: Results for C2 with knowledge graph in Figure 3

  3. 3.

C3: What are the available actions for ’blocksworld’ domain?
Question Type: Extracting domain information.
Sufficiency Condition: For the ’blocksworld’ individual of `PlanningDomain`,
there must be at least one `DomainAction` individual with the relation
`hasAction`.
Result: Shown in Table 3.

S.No | Domain | Relation | Action
---|---|---|---
1 | blocksworld | hasAction | put-down
2 | blocksworld | hasAction | pick-up
3 | blocksworld | hasAction | stack
4 | blocksworld | hasAction | unstack
Table 3: Results for C3 with knowledge graph in Figure 3

  4. 4.

C4: Which problems in ’blocksworld’ have problems with the goal state of ’b1’
being on the table?
Question Type: Extracting problem information
Sufficiency Condition: For the ’blocksworld’ individual of `PlanningDomain`,
there must be at least one `PlanningProblem` individual with the relation
`hasProblem` and the problem should have ’(ontable b1)’ `GoalState`.
Result: Shown in Table 4.

S.No | Domain | Relation | Problem
---|---|---|---
1 | blocksworld | hasProblem | problem_3_1
Table 4: Results for C4 with knowledge graph in Figure 3

  5. 5.

C5: What are all requirements a given domain has?
Question Type: Extracting domain information
Sufficiency Condition: For the ’blocksworld’ individual of `PlanningDomain`,
there must exist at least one `DomainRequirement` individual with the relation
`hasRequirement`.
Result: Shown in Table 5.

S.No | Domain | Relation | Requirement
---|---|---|---
1 | blocksworld | hasRequirement | :strips
Table 5: Results for C5 with knowledge graph in Figure 3

Domain | Ontology Policy | Random Policy
---|---|---
| Avg. Exp. | Avg. Plan Cost | Avg. Exp | Avg. Plan Cost
scanalyzer | 8588 | 20 | 8706 | 20
elevators | 1471 | 52 | 64541 | 52
transport | 165263 | 491 | 132367 | 491
parking* | 367910 | 18 | 488830 | 17
woodworking | 1988 | 211 | 19844 | 211
floortile** | 283724 | 54 | 2101 | 49
barman | 1275078 | 90 | 5816476 | 90
openstacks | 132956 | 4 | 139857 | 4
nomystery | 1690 | 13 | 1690 | 13
pegsol | 89246 | 6 | 101491 | 6
visitall | 5 | 4 | 5 | 4
tidybot** | 1173 | 17 | 3371 | 33
parcprinter | 541 | 441374 | 417 | 441374
sokoban | 9653 | 25 | 156600 | 25
Table 6: Demonstrating the effectiveness of two different policies employed to
choose a planner for problem-solving.

####  5.0.2 Usecase 1: Identifying Most Promising Planner

\- One of the major challenges in the field of artificial intelligence (AI) is
the automated selection of the best-performing planner for a given planning
domain. This challenge arises due to the vast number of available planners and
the diversity of planning domains. To address this challenge, our approach
proposes the use of an ontology to represent the features of the planning
domain and the capabilities of planners.

The ontology for planning aims to capture the connection between the Planning
Domain and the Planner by indicating the relevance of a planner to a specific
domain. We made use of data acquired from International Planning Competitions
(IPCs) to furnish specific details regarding the relevance of planners. The
IPC results provide us with relevant details on the planners that took part in
the competition and the domains that were evaluated during that particular
year. This information includes specifics on how each planner performed
against all the domains that participated.

To show the usage of extracting the most promising planners for a given
domain, we have used IPC-2011
data333http://www.plg.inf.uc3m.es/ipc2011-deterministic/ (optimal track). The
ontology was populated with data acquired from the IPC-2011, which provided
relevant details on the planners that took part in the competition and the
domains that were evaluated during IPC-2011. A relevance relation of either
low, medium, or high was assigned to each planner based on the percentage,
low-below 35%, medium-35% to 70%, high-70% and above, of problems they solved
in a given domain. In this experiment, we consider that the experimental
environment has four planners available: Fast Downward Stone Soup
1444https://www.fast-downward.org/IpcPlanners, LM-Cut4, Merge and Shrink4, and
BJOLP4. We evaluate 3 problem instances of each domain from IPC-2011 with 2
policies for selecting planners to generate plans for each of these problem
instances -

  1. 1.

Random Policy: To solve each problem instance, this policy selects a random
planner from the available planners.

  2. 2.

Ontology Policy: To solve each problem instance, this policy extracts the
information on the best planner for the problem domain from the ontology
populated with IPC-2011 data.

Table 6 presents the results of our evaluation, indicating the average number
of nodes expanded and plan cost for each policy in a given domain. The table
provides a comprehensive summary of the performance of different planners in
terms of their efficiency and effectiveness. An ideal planner is expected to
generate a solution with low values for both these metrics. The Ontology
Policy, designed to select the best-performing planner for a given domain,
outperformed the Random Policy in terms of the average number of nodes
expanded to find a solution. Moreover, the Random Policy failed to solve
problems in the ’parking’ (1 out of 3), ’floortile’ (2 out of 3), and
’tidybot’ (2 out of 3) domains, which highlights the limitations of choosing a
planner randomly. But if a domain is easily solvable by relevant planners that
can tackle them, Random Policy may still do well.

####  5.0.3 Usecase 2: Extracting Macro Operators

\- While automated planning has been successful in many domains, it can be
computationally expensive, especially for complex problems. One approach to
improve efficiency is by using macro-operators, which are sequences of
primitive actions that can be executed as a single step. However, identifying
useful macro-operators manually can be time-consuming and challenging. Authors
in [3] introduce a novel method for improving the efficiency of planners by
generating macro-operators. The proposed approach involves analyzing the
inter-dependencies between actions in plans and extracting macro-operators
that can replace primitive actions without losing the completeness of the
problem domain. The soundness and complexity of the method are assessed and
compared to other existing techniques. The paper asserts that the generated
macro-operators are valuable and can be seamlessly integrated into planning
domains without losing the completeness of the problem.

Based on the ontology depicted in Figure 2, we extract macro-operators that
can enhance the efficiency of planners. To demonstrate this, we have
considered three different domains: `blocksworld`(bw), `driverlog`(dl), and
`grippers`(gr), presented in IPC-2000, 2002, and 1998 respectively. We
initially developed a knowledge graph using the ontology represented in Figure
2 for the three domains of interest. Subsequently, we employed a SPARQL query
to retrieve the stored plans for these domains. We then examined these plans
to identify the sequences of action pairs and ranked them based on their
frequency of occurrence. To improve the effectiveness of this technique, it is
essential to consider both the frequency of occurrence of action pairs and the
properties of the domain. Specifically, the precondition and effect of actions
should be analyzed to ensure that the first action leads to the precondition
of the second action in the pair. We employed another SPARQL query to extract
the preconditions and effects associated with each of these actions. We
analyzed the resulting action pairs to verify their validity of occurrence,
thereby filtering out pairs that did not have a combined effect. The results
of this extraction process are shown in Table 7. These action relations are
stored back into the knowledge graph in the `MacroAction` class and can be
utilized by planners to enhance their efficiency.

Domains |  Extracted Action Relations
---|---
blocksworld |  unstack * put-down; pick-up * stack; put-down * unstack; stack * pick-up; unstack * stack; put-down * pick-up; stack * unstack
driverlog |  drive-truck * unload-truck; drive-truck * load-truck; board-truck * drive-truck; walk * board-truck
grippers |  pick * move; move * drop
Table 7: Extracted action relations, ordered based on their frequency, for domains blocksworld, driverlog, and grippers. Domain | Original Domain | Domain With Macros
---|---|---
| Avg. Exp. | Avg. Eval. | Avg. Gen. | Avg. Exp. | Avg. Eval. | Avg. Gen.
blocksworld | 20219 | 59090 | 106321 | 18 | 310 | 359
gripper | 2672 | 10660 | 30871 | 510 | 3974 | 11468
driverlog | 3753 | 17849 | 45753 | 14888 | 720008 | 209760
Table 8: Comparison of planner performance between original and macro-enabled
versions of three planning domains, showing the average number of nodes
expanded, evaluated, and generated.

Table 8 shows the comparison of a planner performance given the original
domain and macros-enabled version of the domain. For this evaluation, we have
considered the FastDownward planner [8] with LM-Cut Heuristic [9] to generate
plans for 20 problems of varying complexities for each domain. We evaluate the
performance of each domain based on the average number of nodes expanded,
evaluated, and generated to find a solution. This study demonstrates that
macro operators can enhance the planner performance in most of the domains
tested, with the exception of the `driverlog` domain. In this domain, the
planner performs worse when macro operators are included, as they increase the
average number of nodes expanded, evaluated, and generated. This is due to the
fact that the macro operators introduce more actions to the domain, which
increases the branching factor and challenges the heuristic to select the
optimal action at each step. Hence, the applicability of macro operators
depends on the features of the domain and the planner. Macro operators can
facilitate the planning process by decreasing the search depth, but they can
also hinder it by increasing the search width. A potential improvement is to
use a more informative heuristic that guides the planner to choose the best
action at each step.

##  6 Conclusion

In this work, we build and share a planning ontology that provides a
structured representation of concepts and relations for planning, allowing for
efficient extraction of domain, problem, and planner properties. The
ontology’s practical utility is demonstrated in identifying the best-
performing planner for a given domain and extracting macro operators using
plan statistics and domain properties. Standardized benchmarks from IPC
domains and planners offer an objective and consistent approach to evaluating
planner performance, enabling rigorous comparisons in different domains to
identify the most suitable planner. The planning ontology can aid researchers
and practitioners in automated planning, and its use can simplify planning
tasks and boost efficiency. As the field of AI planning continues to evolve,
planning ontology can play a crucial role in advancing the state-of-the-art
while leveraging the past.

Future work could explore the use of mixed reasoning strategy with both
ontologies (top-down) and Large Language Models (LLMs) (bottom-up) knowledge
[10]. For instance, one could leverage the planning ontology in the context of
LLMs, which have recently shown promise for automated planning [12]. Moreover,
the application of this mixed reasoning approach could be extended to complex
domains, such as multi-agent systems, where coordinating actions between
multiple agents is crucial.

## References

  * [1] Babli, M., Onaindia, E., Marzal, E.: Extending planning knowledge using ontologies for goal opportunities. arXiv preprint arXiv:1904.03606 (2019)
  * [2] Bihl, T.J., Cox, C., Machin, T.: Towards a taxonomy of planning for autonomous systems. In: 2019 IEEE National Aerospace and Electronics Conference (NAECON). pp. 74–79 (2019). https://doi.org/10.1109/NAECON46414.2019.9058324
  * [3] Chrpa, L.: Generation of macro-operators via investigation of action dependencies in plans. The Knowledge Engineering Review 25(3), 281–297 (2010)
  * [4] Gayathri, R., Uma, V.: Ontology based knowledge representation technique, domain modeling languages and planners for robotic path planning: A survey. ICT Express 4(2), 69–74 (2018)
  * [5] Ghallab, M., Nau, D., Traverso, P.: Automated Planning: theory and practice. Elsevier (2004)
  * [6] Gil, Y., Blythe, J.: Planet: A shareable and reusable ontology for representing plans. In: AAAI Workshop on Representational Issues for Real-world Planning Systems. Website: https://www.isi.edu/b̃lythe/planet/. vol. 114 (2000)
  * [7] Guarino, N., Oberle, D., Staab, S.: What is an ontology? Handbook on ontologies pp. 1–17 (2009)
  * [8] Helmert, M.: The fast downward planning system. Journal of Artificial Intelligence Research 26, 191–246 (2006)
  * [9] Helmert, M., Domshlak, C.: Lm-cut: Optimal planning with the landmark-cut heuristic. Seventh international planning competition (IPC 2011), deterministic part pp. 103–105 (2011)
  * [10] Mittal, S., Joshi, A., Finin, T.W.: Thinking, fast and slow: Combining vector spaces and knowledge graphs. ArXiv abs/1708.03310 (2017)
  * [11] Muppasani, B., Pallagani, V., Srivastava, B., Mutharaju, R.: Building and using a planning ontology from past data for performance efficiency. In: Proceedings of the PLanning And onTology wOrkshop (PLATO), co-located with the 33rd International Conference on Automated Planning and Scheduling (ICAPS’23) (2023)
  * [12] Pallagani, V., Muppasani, B., Murugesan, K., Rossi, F., Horesh, L., Srivastava, B., Fabiano, F., Loreggia, A.: Plansformer: Generating symbolic plans using transformers. In: On Arxiv at: https://arxiv.org/abs/2212.08681 (2022)
  * [13] Valente, A., Russ, T., MacGregor, R., Swartout, W.: Building and (re) using an ontology of air campaign planning. IEEE Intelligent Systems and their Applications 14(1), 27–36 (1999)
  * [14] Wilkinson, M.D., Dumontier, M., Aalbersberg, I.J., Appleton, G., Axton, M., Baak, A., Blomberg, N., Boiten, J.W., da Silva Santos, L.B., Bourne, P.E., et al.: The fair guiding principles for scientific data management and stewardship. Scientific data 3 (2016)
  * [15] Žáková, M., Křemen, P., Železnỳ, F., Lavrač, N.: Automating knowledge discovery workflow composition through ontology-based planning. IEEE Transactions on Automation Science and Engineering 8(2), 253–264 (2010)


# Effective descent morphisms of ordered families

Maria Manuel Clementino  University of Coimbra, CMUC, Department of
Mathematics, 3000-143 Coimbra, Portugal<EMAIL_ADDRESS>and  Rui Prezado
University of Coimbra, CMUC, Department of Mathematics, 3000-143 Coimbra,
Portugal<EMAIL_ADDRESS>
(Date: 1st September 2024)

###### Abstract.

We present a characterization of effective descent morphisms in the lax comma
category $\mathsf{Ord}//X$ when $X$ is a locally complete ordered set with a
bottom element.

###### Key words and phrases:

effective descent morphisms, Grothendieck descent theory, stable regular
epimorphisms, lax comma categories, ordered families, free coproduct
completion

###### 1991 Mathematics Subject Classification:

06A07,18A25,18A30,18B35,18B50,18D30

The authors acknowledge partial financial support by Centro de Matemática da
Universidade de Coimbra (CMUC), funded by the Portuguese Government through
FCT/MCTES, DOI 10.54499/UIDB/00324/2020.

## Introduction

The role of lax comma 2-categories in [7], where the authors study properties
of the lax change-of-base functor in the realm of Janelidze’s Galois theory
[9, 1] led Lucatelli Nunes and the first named author of this note to study
the behaviour of the lax comma category $\mathsf{Ord}//X$ of ordered sets over
a fixed ordered set $X$, in [6]. Objects of $\mathsf{Ord}//X$ are ordered sets
$A$ equipped with a monotone map $\alpha\colon A\to X$, which assigns to each
element of $A$ an $X$-value, and a morphism $f\colon(A,\alpha)\to(B,\beta)$ is
a monotone map that does not increase $X$-values, so that
$\alpha(a)\leq\beta(f(a))$ for every $a\in A$.

In particular, a study of the effective descent morphisms in $\mathsf{Ord}//X$
was carried out in [6], when $X$ is a complete ordered set, locating them
between two well-known classes of monotone maps, as stated in Theorem 1.3.
Subsequently, these results were refined in [5], extending them to the case
when $X$ is locally complete (Theorem 1.4).

In this note, we obtain a complete characterization of the effective descent
morphisms in $\mathsf{Ord}//X$ when $X$ is locally complete, that is,
$\downarrow x$ is complete for every $x\in X$, and has a bottom element. This
is accomplished by reducing the problem to the study of effective descent
morphisms in $\mathsf{Ord}$ – which were characterized in [10] – and in
$\mathsf{Fam}(X)$ – which were characterized by the second author in [17].

We begin by recalling the necessary descent theoretical background, and by
giving an overview of previously obtained results on effective descent
morphisms in $\mathsf{Ord}//X$ in the prequels [6, 5].

In particular, it is well-understood that $\mathsf{Ord}//X\to\mathsf{Ord}$
preserves effective descent morphisms when $X$ has a bottom element. Our main
observation is that we can complete the characterization via effective descent
conditions on morphisms in the category $\mathsf{Fam}(X)$. Thus, we recount
the relevant details about such morphisms from [17], framed in our context. We
also revisit the characterization of stable regular epimorphisms in
$\mathsf{Ord}//X$ from [6] from the perspective of the work carried out in
[17].

We conclude the paper by stating and proving our main result (Theorem 3.1),
where we characterize the effective descent morphisms in $\mathsf{Ord}//X$
when $X$ has a bottom element and is locally complete, that is, $\downarrow x$
is complete for all $x$.

##  1\. State-of-the-art

In a category $\mathsf{A}$ with pullbacks, any morphism $p\colon A\to B$
induces a functor $p^{*}\colon\mathsf{A}/B\to\mathsf{A}/A$, by taking
pullbacks along $p$. This functor has a left adjoint $p_{!}$, and this induces
a monad $T^{p}$, so we may consider the factorization of $p^{*}$ through the
category of $T^{p}$-algebras (the Eilenberg-Moore factorization):

(1.i)
${\mathsf{A}/B}$${\mathsf{A}/A}$${T^{p}\text{-}\mathsf{Alg}}$$\scriptstyle{K^{p}}$$\scriptstyle{p^{*}}$

By the Bénabou-Roubaud theorem [2], the factorization (1.i) coincides with the
descent factorization [13, 16] of $p$ – a result which allows the aptly called
the monadic description of descent [12].

We say that

  * –

$p$ is a descent morphism if $K^{p}$ is fully faithful,

  * –

$p$ is an effective descent morphism if $K^{p}$ is an equivalence.

In a category $\mathsf{A}$ with finite limits, the descent morphisms are
exactly (pullback-)stable regular epimorphisms, which coincide with the
effective descent morphisms when $\mathsf{A}$ is Barr-exact or locally
cartesian closed (see [11] for details).

However, in an arbitrary category $\mathsf{A}$ with pullbacks, the
identification of effective descent morphisms may be quite challenging – a
notorious example is the characterization of effective descent morphisms in
the category $\mathsf{Top}$ of topological spaces [19, 3].

A fruitful strategy to understand effective descent morphisms in an arbitrary
category $\mathsf{A}$ with pullbacks is to find a category $\mathsf{D}$ with
pullbacks for which the effective descent morphisms are well-understood, and a
suitable embedding $F\colon\mathsf{A}\to\mathsf{D}$. Then, we may apply the
following classical result:

######  Theorem 1.1.

Let $\mathsf{A}$ and $\mathsf{D}$ be categories with pullbacks, and
$F\colon\mathsf{A}\to\mathsf{D}$ a fully faithful, pullback preserving
functor. If $f\colon A\to B$ is a morphism in $\mathsf{A}$ such that $F(f)$ is
effective for descent in $\mathsf{D}$, then the following conditions are
equivalent:

  1. (i)

$f$ is an effective descent morphism in $\mathsf{A}$;

  2. (ii)

for every pullback diagram of the form

${F(C)}$${E}$${F(A)}$${F(B)}$$\scriptstyle{g}$$\scriptstyle{F(f)}$

we have $E\cong FD$ for some $D$ in $\mathsf{A}$.

This technique was used in [10] by G. Janelidze and M. Sobral to obtain the
characterization of effective descent morphisms in the category $\mathsf{Ord}$
of ordered sets (that is, sets with a reflexive and transitive relation) and
monotone maps:

######  Theorem 1.2 ([10]).

Given a morphism $f\colon A\to B$ in $\mathsf{Ord}$:

  1. (1)

$f$ is a descent morphism, or, equivalently, a stable regular epimorphism, if:

$\forall b_{0}\leq b_{1}\mbox{ in }B,\;\;\exists a_{0}\leq a_{1}\mbox{ in
}A\;\;:\;\;f(a_{0})=b_{0},\;f(a_{1})=b_{1};$

  2. (2)

$f$ is an effective descent morphism if:

$\forall b_{0}\leq b_{1}\leq b_{2}\mbox{ in }B,\;\;\exists a_{0}\leq a_{1}\leq
a_{2}\mbox{ in }A\;\;:\;\;f(a_{0})=b_{0},\;f(a_{1})=b_{1},\;f(a_{2})=b_{2}.$

Moreover, Theorem 1.1 is also used in [6] and [5] to study the effective
descent morphisms in $\mathsf{Ord}//X$. This result is also featured in the
present note.

We note that, while the characterizations of Theorem 1.1 extend naturally to
the comma categories $\mathsf{Ord}/X$ via the equivalence

$(\mathsf{Ord}/X)/(B,\beta)\simeq\mathsf{Ord}/B,$

this is not the case of the lax comma category $\mathsf{Ord}//X$, of which
$\mathsf{Ord}/X$ is a wide subcategory (i.e. with the same objects but fewer
morphisms).

In [6], the authors make use of Theorem 1.1 and of the fact that every
monotone map $\alpha\colon A\to X$ induces naturally a functor
$\Pi(\alpha)\colon X^{\mathsf{op}}\to\mathsf{Ord}$, so that a morphism
$f\colon(A,\alpha)\to(B,\beta)$ induces a natural transformation
$\Pi(\alpha)\to\Pi(\beta)$. Indeed:

  * –

for a complete ordered set $X$, one defines an embedding

$\textstyle{\mathsf{Ord}//X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Pi}$$\textstyle{[X^{\mathsf{op}},\mathsf{Ord}]}$

with $\Pi(A,\alpha)(x)=\\{a\in A\,;\,x\leq\alpha(a)\\}$ and $\Pi(f)$ given by
the (co)restriction of $f$ to $\Pi(A,\alpha)(x)\to\Pi(B,\beta)(x)$: from
$\alpha\leq\beta f$ it follows that if $x\leq\alpha(a)$ then
$x\leq\beta(f(a))$;

  * –

in $[X^{\mathsf{op}},\mathsf{Ord}]$ a natural transformation $\eta\colon F\to
G$ is effective for descent if and only if it is pointwise effective for
descent, that is: for every $x\in X$, the monotone map $\eta_{x}\colon F(x)\to
G(x)$ is effective for descent in $\mathsf{Ord}$.

######  Theorem 1.3 ([6]).

Let $X$ be a complete ordered set. Given a morphism
$f\colon(A,\alpha)\to(B,\beta)$ in $\mathsf{Ord}//X$, consider the following
conditions:

  1. (1)

$f\colon A\to B$ and all $f_{x}\colon A_{x}\to B_{x}$ are effective descent
morphisms in $\mathsf{Ord}$;

  2. (2)

$f\colon(A,\alpha)\to(B,\beta)$ is effective for descent in $\mathsf{Ord}//X$;

  3. (3)

$f\colon A\to B$ is effective for descent in $\mathsf{Ord}$.

Then _(1) $\Rightarrow$ (2) $\Rightarrow$ (3)_.

Subsequently, in [5] the authors use the fact that every monotone map
$\alpha\colon A\to X$ naturally defines a family $(A_{x})_{x\in X}$ of subsets
of $A$ such that $A_{x}\subseteq A_{x^{\prime}}$ whenever $x^{\prime}\leq x$,
and that every monotone map $f\colon(A,\alpha)\to(B,\beta)$ satisfies
$f(A_{x})\subseteq B_{x}$ for each $x\in X$. Considering the category
$\mathsf{C}$ having

  * –

as objects, pairs $(A,(A_{x})_{x\in X})$, where $A$ is an ordered set and
$(A_{x})_{x\in X}$ is a family of subsets of $A$ such that $A_{x}\subseteq
A_{x^{\prime}}$ whenever $x^{\prime}\leq x$,

  * –

and as morphisms $f\colon(A,(A_{x}))\to(B,(B_{x}))$, monotone maps $f\colon
A\to B$ such that $f(A_{x})\subseteq B_{x}$ for each $x\in X$,

one can apply Theorem 1.1 based on the following facts:

  * –

the functor

$\textstyle{\mathsf{Ord}//X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{F}$$\textstyle{\mathsf{C},}$

defined by $F(A,\alpha)=(A,(A_{x}=\\{a\in A,\;\,x\leq\alpha(a)\\})_{x})$ and
$F(f)=f$, is fully faithful and preserves pullbacks;

  * –

a morphism $f\colon(A,(A_{x})_{x})\to(B,(B_{x})_{x})$ is effective for descent
in $\mathsf{C}$ if and only if $f\colon A\to B$ and $f_{x}\colon A_{x}\to
B_{x}$ for all $x\in X$ are surjective.

######  Theorem 1.4 ([5]).

Let $X$ be a locally complete ordered set. For a morphism
$f\colon(A,\alpha)\to(B,\beta)$ in $\mathsf{Ord}//X$, consider the following
conditions:

  1. (1)

In $\mathsf{Ord}$, $f\colon A\to B$ is effective for descent, and $f_{x}\colon
A_{x}\to B_{x}$ is a descent morphism for all $x\in X$;

  2. (2)

$f\colon(A,\alpha)\to(B,\beta)$ is effective for descent in $\mathsf{Ord}//X$.

Then _(1) $\Rightarrow$ (2)_. If, in addition, for each $x\in X$ every subset
of $\downarrow x$ has a largest element, then _(1) $\Leftrightarrow$ (2)_.

Theorem 1.4 gives us, for a locally complete ordered set $X$, a sufficient
condition for $f$ to be effective for descent in $\mathsf{Ord}//X$ which is
not necessary in general, as we show in the sequel. Indeed, in order to apply
Theorem 1.1, we must start with a morphism whose $F$-image is an effective
descent morphism in $\mathsf{C}$, hence $f$ and all $f_{x}$ are a priori
surjective, and this condition is not fulfilled by all effective descent
morphisms in $\mathsf{Ord}//X$, as we show in Example 3.4.

##  2\. Familial descent

One of the main insights behind our main result, Theorem 3.1, is that we can
reduce the study of effective descent morphisms (respectively, stable regular
epimorphisms) in $\mathsf{Ord}//X$ to the study of effective descent morphisms
(respectively, stable regular epimorphisms) in $\mathsf{Fam}(X)$ and
$\mathsf{Ord}$. This latter problem in $\mathsf{Fam}(X)$ has been considered
before in [17, Lemma 4.4] (see also [18, Lemma 3.17]), from which we proceed
to recall the relevant details.

For a fixed ordered set $X$, we denote by $\mathsf{Fam}(X)$ the category of
set-indexed families of elements in $X$. It consists of:

  * –

Objects: families $(\alpha_{j})_{j\in J}$ of elements $\alpha_{j}\in X$
indexed by a set $J$,

  * –

Morphisms $(\alpha_{j})_{j\in J}\to(\beta_{k})_{k\in K}$: a function $f\colon
J\to K$ such that $\alpha_{j}\leq\beta_{f(j)}$ for all $j\in J$.

We will assume that locally $X$ has binary meets, that is, $\downarrow x$ has
binary meets for all $x$. When $X$ is seen as a thin category, this condition
is equivalent to saying that $X$ has pullbacks. Thus, it follows that
$\mathsf{Fam}(X)$ is a category with pullbacks (see [1, Sections 6.2, 6.3]).

While the results of [17, 18] study (effective) descent morphisms in
$\mathsf{Fam}(X)$ when $X$ has a top element, this was due to the pertinence
of the work carried out within, and the results plainly extend to the setting
where $X$ does not admit a top element.

######  Lemma 2.1 ([17, Lemma 4.4], [18, Lemma 3.17]).

Let $f\colon(\alpha_{j})_{j\in J}\to(\beta_{k})_{k\in K}$ be a morphism in
$\mathsf{Fam}(X)$.

  1. (1)

$f$ is a descent morphism if and only if, for all $k\in K$ and all
$z\leq\beta_{k}$, we have

(2.i) $z\cong\operatorname*{\bigvee}_{f(j)=k}z\wedge\alpha_{j}$

  2. (2)

If $X$ is locally complete, then $f$ is an effective descent morphism if and
only if $f$ is a descent morphism.

###### Proof.

We verify that having a top element is redundant.

By [11, Theorem 3.4(a)], we note that $f$ is a descent morphism in
$\mathsf{Fam}(X)$ if and only if it is a stable regular epimorphism in

$\mathsf{Fam}(X)/(\beta_{k})_{k\in K}\simeq\prod_{k\in
K}\mathsf{Fam}(X)/\beta_{k}\simeq\prod_{k\in K}\mathsf{Fam}(X/\beta_{k}),$

which is the case if and only if (2.i) holds. ∎

Lemma 2.1 on its own already allows us to smoothly extend the characterization
of stable regular epimorphisms obtained in [6, Lemma 3.1, Proposition 3.2] for
$X$ complete and cartesian closed to our context.

######  Lemma 2.2.

Let $X$ be locally complete ordered set with a bottom element, and let
$f\colon(A,\alpha)\to(B,\beta)$ be a morphism in $\mathsf{Ord}//X$.

  1. (1)

$f$ is a regular epimorphism in $\mathsf{Ord}//X$ if and only if it is a
regular epimorphism in $\mathsf{Ord}$ and

$\forall b\in B\;\;\;\beta(b)\cong\operatorname*{\bigvee}_{f(a)\leq
b}\beta(b)\wedge\alpha(a).$

  2. (2)

$f$ is a stable regular epimorphism in $\mathsf{Ord}//X$ if and only if it is
a stable regular epimorphism in $\mathsf{Ord}$ and

(2.ii) $\forall b\in B\;\;\forall
x\leq\beta(b)\;\;x\cong\operatorname*{\bigvee}_{f(a)=b}x\wedge\alpha(a).$

###### Proof.

Statement (1) is precisely [6, Lemma 3.1], so we focus on (2).

If $f$ is a stable regular epimorphism in $\mathsf{Ord}//X$, then, for each
$b\in B$ and $x\leq\beta(b)$, we consider the pullback diagram

${\Big{(}f^{-1}(b),\big{(}a\mapsto
x\wedge\alpha(a)\big{)}\Big{)}}$${(b,x)}$${(A,\alpha)}$${(B,\beta)}$$\scriptstyle{u}$$\scriptstyle{f}$

so that $u$ is a regular epimorphism in $\mathsf{Ord}//X$, which entails
(2.ii), as desired.

Conversely, if (2.ii) holds for all $b\in B$ and all $x\leq\beta(b)$, then for
any pullback diagram

${\Big{(}A\times_{B}C,\big{(}(a,c)\mapsto\gamma(c)\wedge\alpha(a)\big{)}\Big{)}}$${(C,\gamma)}$${(A,\alpha)}$${(B,\beta)}$$\scriptstyle{\pi_{2}}$$\scriptstyle{g}$$\scriptstyle{f}$

we claim that $\pi_{2}$ is a (stable) regular epimorphism. Indeed, for each
$c\in C$ we have $\gamma(c)\leq\beta(g(c))$, so from (2.ii) we deduce that

$\gamma(c)\cong\operatorname*{\bigvee}_{f(a)=g(c)}\gamma(c)\wedge\alpha(a)\cong\operatorname*{\bigvee}_{\begin{subarray}{c}f(a^{\prime})=g(c^{\prime})\\\
c^{\prime}\leq c\end{subarray}}\gamma(c^{\prime})\wedge\alpha(a^{\prime})$

which indeed confirms that $\pi_{2}$ is a regular epimorphism. ∎

######  Remark 2.3.

We point out that condition (2.ii) can be interpreted in the category
$\mathsf{Fam}(X)$ by considering the (faithful) forgetful functor

$\textstyle{\mathsf{Ord}//X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{Fam}(X)}$

which maps $(A,\alpha)$ to the family $(\alpha(a))_{a\in A}$. Thus, by Lemma
2.1, condition (2) can be restated as follows: $f\colon(A,\alpha)\to(B,\beta)$
is a stable regular epimorphism in $\mathsf{Ord}//X$ if and only if the
underlying morphisms in $\mathsf{Ord}$ and $\mathsf{Fam}(X)$ are stable
regular epimorphisms.

In fact, we can say more: since $X$ is assumed to be locally complete,
$U\colon\mathsf{Ord}//X\to\mathsf{Fam}(X)$ maps stable regular epimorphisms to
effective descent morphisms. Therefore, when $X$ is locally complete and has a
bottom element, we conclude that both forgetful functors

(2.iii) ${\mathsf{Ord}//X}$${\mathsf{Ord}}$${\mathsf{Fam}(X)}$

preserve effective descent morphisms.

##  3\. The characterization

Having reviewed the necessary details, we may proceed to prove our main
result:

######  Theorem 3.1.

Let $X$ be a locally complete ordered set. A morphism
$f\colon(A,\alpha)\to(B,\beta)$ is effective for descent in $\mathsf{Ord}//X$
if and only if

  1. (a)

$f\colon A\to B$ is effective for descent in $\mathsf{Ord}$; that is

$\forall b_{0}\leq b_{1}\leq b_{2}\text{ in }B\;\;\exists a_{0}\leq a_{1}\leq
a_{2}\text{ in }A\colon\quad
f(a_{0})=b_{0},\;f(a_{1})=b_{1},\;f(a_{2})=b_{2}.$

  2. (b)

for all $b_{0}\leq b_{1}$ in $B$, and all $w\leq\beta(b_{0})$ in $X$, we have

$w=\operatorname*{\bigvee}_{a_{0}\in S_{b_{0},b_{1}}}w\wedge\alpha(a_{0}),$

where $S_{b_{0},b_{1}}=\\{a_{0}\in f^{-1}(b_{0})\;|\;\exists a_{1}\in
f^{-1}(b_{1})\text{ with }a_{0}\leq a_{1}\\}$.

To prove this result, it is natural to consider the (pseudo)pullback diagram
below (see [14], noting that $\mathsf{Fam}(X)\to\mathsf{Set}$ is an
(iso)fibration):

${\mathsf{Ord}\times_{\mathsf{Set}}\mathsf{Fam}(X)}$${\mathsf{Fam}(X)}$${\mathsf{Ord}}$${\mathsf{Set}}$$\scriptstyle{\rho_{1}}$$\scriptstyle{\rho_{2}}$

as well as the uniquely induced functor
$\mathsf{Ord}//X\to\mathsf{Ord}\times_{\mathsf{Set}}\mathsf{Fam}(X)$ induced
by the forgetful functors (2.iii).

Using either [5, Corollary 2.6] or [15, Corollary 9.6], we obtain:

######  Lemma 3.2.

Let $X$ be a locally complete ordered set with a bottom element. A morphism
$f$ is effective for descent in
$\mathsf{Ord}\times_{\mathsf{Set}}\mathsf{Fam}(X)$ if and only if:

  1. (1)

$\rho_{1}(f)$ is effective for descent in $\mathsf{Ord}$.

  2. (2)

$\rho_{2}(f)$ is effective for descent in $\mathsf{Fam}(X)$.

Now, the fully faithful and pullback preserving functor

$\textstyle{\mathsf{Ord}//X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{U}$$\textstyle{\mathsf{Ord}\times_{\mathsf{Set}}\mathsf{Fam}(X)}$

and Theorem 1.1 give us the tools to characterize effective descent morphisms
in $\mathsf{Ord}//X$. Before proceeding to the proof, we recall that the
objects $\mathsf{Ord}\times_{\mathsf{Set}}\mathsf{Fam}(X)$ consist of pairs
$(C,(\chi_{c})_{c\in C})$ where $C$ is an ordered set and $(\chi_{c})_{c\in
C}$ is a family of elements of $X$, that is, a map $\chi\colon C\to X$. Such a
pair is in the (essential) image of $U$ if and only if $\chi$ is monotone.

###### Proof of Theorem 3.1.

Let $f\colon(A,\alpha)\to(B,\beta)$ be a morphism in $\mathsf{Ord}//X$.

If (b) holds, we note that for all $b_{0}\leq b_{1}$ in $B$ and all
$w\leq\beta(b_{0})$ in $X$, we have

$w\cong\operatorname*{\bigvee}_{a_{0}\in
S_{b_{0},b_{1}}}w\wedge\alpha(a_{0})\leq\operatorname*{\bigvee}_{a_{0}\in
f^{-1}(b_{0})}w\wedge\alpha(a_{0})\leq w,$

hence $\rho_{2}(U(f))$ is an effective descent morphism in $\mathsf{Fam}(X)$
by Lemma 2.1. Thus, if (a) also holds, $\rho_{1}(U(f))$ is an effective
descent morphism in $\mathsf{Ord}$, so $U(f)$ is an effective descent morphism
in $\mathsf{Ord}\times_{\mathsf{Set}}\mathsf{Fam}(X)$.

Now, we apply Theorem 1.1: if we have a pullback diagram

$\textstyle{U(D,\delta)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{(C,(\chi_{c})_{c\in
C})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\textstyle{U(A,\alpha)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{U(f)}$$\textstyle{U(B,\beta)}$

we want to show that $\chi\colon C\to X$ is monotone. Let $c_{0}\leq c_{1}\in
C$, $b_{i}=g(c_{i})$, $i=0,1$, and let $S_{b_{0},b_{1}}=\\{a_{0}\in
f^{-1}(b_{0})\;|\;\exists a_{1}\in f^{-1}(b_{1})\text{ with }a_{0}\leq
a_{1}\\}$. Then $\chi(c_{0})\leq\beta(b_{0})$ and therefore, by condition (b),

$\chi(c_{0})\cong\operatorname*{\bigvee}_{a_{0}\in
S_{b_{0},b_{1}}}\chi(c_{0})\wedge\alpha(a_{0})=\operatorname*{\bigvee}_{a_{0}\in
S_{b_{0},b_{1}}}\delta(a_{0},c_{0})\leq\bigvee_{a\in
f^{-1}(b_{1})}\delta(a,c_{1})\leq\chi(c_{1}),$

as desired.

Conversely, if $f$ is an effective descent morphism, then by Remark 2.3, it
follows that both $\rho_{1}(U(f))$ and $\rho_{2}(U(f))$ are effective descent
morphisms in $\mathsf{Ord}$ and $\mathsf{Fam}(X)$, respectively, from which we
conclude that $U(f)$ is an effective descent morphism (by Lemma 3.2), and that
(a) holds.

Again, we apply Theorem 1.1: we let $b_{0}\leq b_{1}$ and $w\leq\beta(b_{0})$,
and we consider the pair
$\big{(}\\{b_{0},b_{1}\\},\big{(}\chi_{b_{0}},\chi_{b_{1}})\big{)}$, where

$\chi_{b_{0}}=w,\qquad\chi_{b_{1}}=\operatorname*{\bigvee}_{a_{0}\in
S_{b_{0},b_{1}}}w\wedge\alpha(a_{0}),$

with $S_{b_{0},b_{1}}=\\{a_{0}\in f^{-1}(b_{0})\,|\;\exists a_{1}\in
f^{-1}(b_{1})\text{ with }a_{0}\leq a_{1}\\}$. We also let

$g\colon\big{(}\\{b_{0},b_{1}\\},(\chi_{b_{0}},\chi_{b_{1}})\big{)}\to(B,\beta)$

be the inclusion. Taking the pullback of $U(f)$ along $g$, we obtain

${\big{(}D,(\xi_{d})_{d\in
D}\big{)}}$${\big{(}\\{b_{0},b_{1}\\},(\chi_{b_{0}},\chi_{b_{1}})\big{)}}$${U(A,\alpha)}$${U(B,\beta),}$$\scriptstyle{g}$$\scriptstyle{U(f)}$

where $D=\\{(a_{i},b_{i})\;|\;f(a_{i})=b_{i},\,i=0,1\\}$, and $\xi$ is given
by

  * –

$\xi_{(a_{0},b_{0})}=\alpha(a_{0})\wedge w$ for each $a_{0}\in A$ such that
$f(a_{0})=b_{0}$, and

  * –

$\xi_{(a_{1},b_{1})}=\alpha(a_{1})\wedge\chi_{b_{1}}$ for each $a_{1}\in A$
such that $f(a_{1})=b_{1}$.

Hence, if $(a_{0},b_{0})\leq(a_{1},b_{1})$, then $a_{0}\leq a_{1}$ and
$f(a_{1})=b_{1}$, so that $a_{0}\in S_{b_{0},b_{1}}$. It follows that

$\alpha(a_{0})\wedge
w\leq\chi_{b_{1}}\qquad\text{and}\qquad\alpha(a_{0})\wedge
w\leq\alpha(a_{1}),$

and therefore $\xi_{a_{0},b_{0}}\leq\xi_{a_{1},b_{1}}$, confirming that $\xi$
is monotone. Thus, $\chi$ must be monotone as well, so that
$\chi_{b_{0}}\cong\chi_{b_{1}}$, confirming that (b) holds. ∎

We recall that an ordered set $X$ with finite meets is said to be cartesian
closed if there is an assignment $(y,z)\mapsto z^{y}$, which satisfies

$x\wedge y\leq z\iff x\leq z^{y}$

for every $x\in X$. When $X$ is complete and the underlying order is
antisymmetric, this is equivalent to $X$ being a frame.

######  Corollary 3.3.

Let $X$ be a cartesian closed, complete ordered set. A morphism
$f\colon(A,\alpha)\to(B,\beta)$ in $\mathsf{Ord}//X$ is an effective descent
morphism if and only if

  1. (a)

$f\colon A\to B$ is effective for descent in $\mathsf{Ord}$; that is

$\forall b_{0}\leq b_{1}\leq b_{2}\text{ in }B\;\;\exists a_{0}\leq a_{1}\leq
a_{2}\text{ in }A\colon\quad
f(a_{0})=b_{0},\;f(a_{1})=b_{1},\;f(a_{2})=b_{2}.$

  2. (b)

for all $b_{0}\leq b_{1}$, we have

$\beta(b_{0})=\operatorname*{\bigvee}_{a_{0}\in
S_{b_{0},b_{1}}}\alpha(a_{0}),$

where $S_{b_{0},b_{1}}=\\{a_{0}\in f^{-1}(b_{0})\;|\;\exists a_{1}\in
f^{-1}(b_{1})\text{ with }a_{0}\leq a_{1}\\}$.

###### Proof.

Since $X$ is cartesian closed, meets distributive over joins, hence we have

$w\cong w\wedge\beta(b_{0})\cong w\wedge\operatorname*{\bigvee}_{a_{0}\in
S_{b_{0},b_{1}}}\alpha(a_{0})\cong\operatorname*{\bigvee}_{a_{0}\in
S_{b_{0},b_{1}}}w\wedge\alpha(a_{0}),$

and we may apply Theorem 3.1. ∎

######  Examples 3.4.

Let $X$ be the interval $[0,1]$ with the usual order – we observe that $X$ is
a cartesian closed, complete ordered set.

Let $A=\\{(x,y)\in X^{2}\,;\,y<x\text{ or }y=x=0\\}$, and write
$\alpha=\pi_{2}$, $f=\pi_{1}$ for the projections.

  1. (1)

If we equip $A$ with the product order, then both $\alpha$ and $f$ are
monotone, so that we have a morphism

(3.i) ${A}$${X}$${X}$$\scriptstyle{\alpha}$${\leq}$$\scriptstyle{f}$

in $\mathsf{Ord}//X$ – indeed, we note that $\alpha(x,y)=y\leq f(x,y)=x$.
Moreover,

     * –

$f$ is effective for descent in $\mathsf{Ord}$:

(3.ii) $\forall x_{0}\leq x_{1}\leq x_{2}\text{ in
}[0,1]\quad\exists(x_{0},0)\leq(x_{1},0)\leq(x_{2},0)\text{ in
}A\;:\;f(x_{i},0)=x_{i}.$

     * –

If $0=x_{0}\leq x_{1}$ then $(0,0)\leq(x_{1},0)$ in $A$ and $0=\alpha(0,0)$;
if $0<x_{0}\leq x_{1}$, then, for all $0\leq y<x$, $(x_{0},y)\leq(x_{1},y)$ in
$A$ and clearly $x_{0}=\bigvee\\{\alpha(x_{0},y)\,|\,0\leq y<x_{0}\\}$,

and these respectively correspond to conditions (a) and (b) of Corollary 3.3.
We conclude that $f$ is an effective descent morphism in $\mathsf{Ord}//X$.

  2. (2)

If we consider on $A$ the order defined by

$(x,y)\leq(x^{\prime},y^{\prime})\iff\quad(x,y)=(x^{\prime},y^{\prime})\quad\text{
or }\quad x\leq x^{\prime}\text{ and }y=y^{\prime}=0,$

then, once again, both $\alpha$ and $f$ are monotone, and $f$ defines a
morphism (3.i) in $\mathsf{Ord}//X$.

Moreover, we note that $f$ is an effective descent morphism in $\mathsf{Ord}$,
since (3.ii) still holds, and that $f$ is a stable regular epimorphism in
$\mathsf{Ord}//X$, because we have $f^{-1}(x)=\\{(x,y)\in A\;|\;0\leq y<x\\}$,
hence

$\forall x\in X\quad x\cong\operatorname*{\bigvee}_{y<x}y.$

While, if $0<x<1$, then $(x_{0},y_{0})\leq(1,y_{1})$ in $A$ only if
$y_{0}=y_{1}=0$, hence

$S_{x_{0},1}=\big{\\{}(x_{0},y_{0})\in A\;|\;y_{0}<x_{0}\text{ and }\exists
y_{1}<1\text{ such that }(x_{0},y_{0})\leq(1,y_{1})\big{\\}}=\\{(x_{0},0)\\},$

and so $f$ does not satisfy (b) of Corollary 3.3.

## References

  * [1] F. Borceux, G. Janelidze.  Galois theories.  Volume 72 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 2001.  DOI: https://doi.org/10.1017/CBO9780511619939
  * [2] J. Bénabou, J. Roubaud.  Monades et descente.  C. R. Math. Acad. Sci. Paris 270(A):96–98, 1970.
  * [3] M.M. Clementino, D. Hofmann.  Triquotient maps via ultrafilter convergence.  Proc. Amer. Math. Soc., 130(11):3423–3431, 2002.  DOI: https://doi.org/10.1090/S0002-9939-02-06472-9
  * [4] M.M. Clementino, D. Hofmann.  The rise and fall of $V$-functors.  _Fuzzy Sets and Systems_ 321:29–49, 2017.  DOI: https://doi.org/10.1016/j.fss.2016.09.005
  * [5] M.M. Clementino, G. Janelidze.  Effective descent morphisms of filtered preorders.  _Order_ , to appear.
  * [6] M.M. Clementino, F. Lucatelli Nunes.  Lax comma categories of ordered sets.  Quaest. Math. 46(S1):145–159, 2023.  DOI: https://doi.org/10.2989/16073606.2023.2247729
  * [7] M.M. Clementino, F. Lucatelli Nunes.  Lax comma 2-categories and admissible 2-functors.  Theory Appl. Categ. 40(6):180–226, 2024.
  * [8] M.M. Clementino, F. Lucatelli Nunes, Rui Prezado.  Lax comma categories: cartesian closedness, extensivity, topologicity, and descent.  Theory Appl. Categ., 41(16):516–530, 2024.
  * [9] G. Janelidze.  Pure Galois theory in categories.  J. Algebra, 132(2):270–286, 1990.  DOI: https://doi.org/10.1016/0021-8693(90)90130-G
  * [10] G. Janelidze, M. Sobral.  Finite preorders and topological descent I.  J. Pure Appl. Algebra, 175:187–205, 2002.  DOI: https://doi.org/10.1016/S0022-4049(02)00134-2
  * [11] G. Janelidze, M. Sobral, W. Tholen.  Beyond Barr exactness: Effective descent morphisms.  In Categorical foundations, pp. 359–405. Encyclopedia Math. Appl., 97. Cambridge Univ. Press, Cambridge, 2004.  DOI: https://doi.org/10.1017/CBO9781107340985.011
  * [12] G. Janelidze, W. Tholen.  Facets of Descent, I.  Appl. Categ. Structures, 2(3):245–281, 1994.  DOI: https://doi.org/10.1023/A:1008697013769
  * [13] G. Janelidze, W. Tholen.  Facets of Descent, II.  Appl. Categ. Structures, 5(3):229–248, 1997.  DOI: https://doi.org/10.1007/BF00878100
  * [14] A. Joyal, R. Street.  Pullbacks equivalent to pseudopullbacks.  Cah. Topol. Géom. Différ. Catég., 34(2):153–156, 1993.
  * [15] F. Lucatelli Nunes.  Pseudo-Kan extensions and descent theory.  _Theory Appl. Categ._ 33(15):390–444, 2018.
  * [16] F. Lucatelli Nunes.  Descent data and absolute Kan extensions.  Theory Appl. Categ., 37(18):530–561, 2021.
  * [17] R. Prezado.  On effective descent $V$-functors and familial descent morphisms.  _J. Pure Appl. Algebra_ 228(5):107597, 2024.  DOI: https://doi.org/10.1016/j.jpaa.2023.107597
  * [18] R. Prezado.  Some aspects of descent theory and applications.  PhD Thesis, University of Coimbra and University of Porto, 2024.  URI: https://hdl.handle.net/10316/114685
  * [19] J. Reiterman, W. Tholen.  Effective descent maps of topological spaces.  Topology Appl., 57:53–69, 1994.  DOI: https://doi.org/10.1016/0166-8641(94)90033-7
  * [20] R.J. Wood.  Ordered Sets via Adjunction.  In Categorical foundations, pp. 5–47. Encyclopedia Math. Appl., 97. Cambridge Univ. Press, Cambridge, 2004.  DOI: https://doi.org/10.1017/CBO9781107340985.004