using Catlab
using AlgebraicRewriting
@present OntBreadOnly(FreeSchema) begin
## Objects
Thing::Ob
BreadLoaf::Ob
BreadSlice::Ob
Countertop::Ob
Stool::Ob
## Morphisms
f::Hom(BreadSlice, BreadLoaf) # is part of
g::Hom(BreadLoaf, Thing) # is-a
h::Hom(Countertop, Thing) # is-a
l::Hom(Stool, Thing) # is-a
## Relations
InOn::Ob
inOn_l::Hom(InOn, Thing)
inOn_r::Hom(InOn, Thing)
end
# Create a C-set type based on ontology
const BreadOnly = DynamicACSet("BreadOnly", OntBreadOnly)A Categorical Representation Language and Computational System for Knowledge-Based Robotic Task Planning
AAAI Unifying Representations for Robot Application Development (URRAD) Fall Symposium 2023
October 25, 2023
Authors
Angeline Aguinaldo
PhD Candidate
University of Maryland, College Park
Johns Hopkins University Applied Physics Laboratory
Evan Patterson
Research Software Engineer
Topos Institute
James Fairbanks
Assistant Professor
University of Florida
William Regli
Professor
University of Maryland, College Park
Jaime Ruiz
Associate Professor
University of Florida
\[ \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\cat}[1]{\mathsf{#1}} \newcommand{\CAT}[1]{\mathsf{#1}} \newcommand{\Set}{\CAT{Set}} \DeclareMathOperator{\Path}{Path} \newcommand{\catSet}[1]{\cat{#1}\text{-}\Set} \DeclareMathOperator{\Ob}{Ob} \DeclareMathOperator{\Hom}{Hom} \]
1.1 Modeling real-world domains for task planning is hard
Let’s imagine ourselves as a domain modeler…
- Want to be able to model everything. Having many objects and relations in a scene can result in a combinatorial explosion of the search space due to the large number of facts.
- Want implicit ontological facts to be preserved after actions are applied. Implicit structure is not propagated when an action is applied, even when using domain axioms (Thiébaux, Hoffmann, and Nebel 2005).
- Want action models to be able to be defined generically. Because structure is not implicitly preserved, it is important that all action effects are accounted for in the action model.
1.2 How is it done today?
(Amiri, Chandan, and Zhang 2022),(Galindo et al. 2008),(Miao, Jia, and Sun 2023),(Agia et al. 2021)
1.3 What is our proposed approach?
2.2 What is a functor and natural transformation?
Definition: A functor, \(F: \cat{C} \rightarrow \cat{D}\), from a category \(\cat{C}\) to a category \(\cat{D}\), has two components, \(F_0\) and \(F_1\), where:
\(F_0\) is a map between objects
\(F_0: \text{Ob}(\cat{C}) \rightarrow \text{Ob}(\cat{D})\)
\(F_1\) is a map between morphism sets
\(F_1: \text{Hom}_\cat{C}(X, Y) \rightarrow \text{Hom}_\cat{D}(F_0(X), F_0(Y))\)
such that,
- \(F_1(g \circ f) = F_1(g) \circ F_1(f)\) for \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\) in \(\cat{C}\)
- \(F_1(1_X) = 1_{F_0(X)}\) for every \(X \in \cat{C}\)
Taken from the nLab
Definition: For functors, \(F: \cat{C} \rightarrow \cat{D}\) and \(G: \cat{C} \rightarrow \cat{D}\), a natural transformation between \(\alpha: F \rightarrow G\) that associates every object in \(C\) and with a morphism in \(D\) such that composition is preserved.
3.1 What is a C-set?
Definition: A \(\cat{C}\)-set is a functor from \(\cat{C} \rightarrow \cat{FinSet}\). \(\cat{FinSet}\) is a category whose objects are finite sets and whose morphisms are set function maps.
Example: An example \(\cat{C}\)-set, called \(G\), that stores data about people’s favorite pet.
The category of elements construction (Riehl 2016) packages the data of \(G\) into a category resembling a knowledge graph (Patterson 2017).
3.2 What is Double-Pushout (DPO) rewrite rule?
Definition: The category \(\catSet{C}\) is a category whose objects are \(\cat{C}\)-set functors and whose morphisms are natural transformations.
Action rules are specified as spans in \(\catSet{C}\).
4.1 Let’s define a world state
For more information about Catlab.jl and AlgebraicRewriting.jl, visit https://www.algebraicjulia.org/.
state = @acset_colim yBreadOnly begin
# Items in the scene
myCountertop::Countertop
myStool::Stool
naturesOwn::BreadLoaf
(slice0, slice1, slice2)::BreadSlice
# Nature's Own Breadloaf has three slices
# f::Hom(BreadSlice, BreadLoaf)
f(slice0) == naturesOwn # is part of
f(slice1) == naturesOwn # is part of
f(slice2) == naturesOwn # is part of
# Breadloaf is on countertop (relation)
thing_on_thing::InOn
inOn_l(thing_on_thing) == naturesOwn
inOn_r(thing_on_thing) == myCountertop
# Breadloaf, counterop, and stool are things
# g::Hom(BreadLoaf, Thing)
# h::Hom(Countertop, Thing)
# l::Hom(Stool, Thing)
(thing1, thing2, thing3)::Thing
g(naturesOwn) == thing1
h(myCountertop) == thing2
l(myStool) == thing3
end
pretty_tables(state)┌───────────┬───┐
│ BreadLoaf │ g │
├───────────┼───┤
│ 1 │ 2 │
└───────────┴───┘
┌────────────┬───┐
│ BreadSlice │ f │
├────────────┼───┤
│ 1 │ 1 │
│ 2 │ 1 │
│ 3 │ 1 │
└────────────┴───┘
┌────────────┬───┐
│ Countertop │ h │
├────────────┼───┤
│ 1 │ 1 │
└────────────┴───┘
┌───────┬───┐
│ Stool │ l │
├───────┼───┤
│ 1 │ 3 │
└───────┴───┘
┌──────┬────────┬────────┐
│ InOn │ inOn_l │ inOn_r │
├──────┼────────┼────────┤
│ 1 │ 2 │ 1 │
└──────┴────────┴────────┘4.2 Let’s define a rewrite rule
d = DRule(@migration(SchRule, OntBreadOnly, begin
L => @join begin
(thing1, thing2)::Thing
breadloaf::BreadLoaf
countertop::Countertop
stool::Stool
g(breadloaf) == thing1
h(countertop) == thing2
thing_on_thing::InOn
inOn_l(thing_on_thing) == breadloaf
inOn_r(thing_on_thing) == countertop
end
K => @join begin
thing::Thing
breadloaf::BreadLoaf
countertop::Countertop
stool::Stool
end
R => @join begin
(thing1, thing2)::Thing
breadloaf::BreadLoaf
countertop::Countertop
stool::Stool
g(breadloaf) == thing1
h(stool) == thing2
thing_on_thing::InOn
inOn_l(thing_on_thing) == breadloaf
inOn_r(thing_on_thing) == stool
end
l => begin
thing => thing1
breadloaf => breadloaf
countertop => countertop
stool => stool
end
r => begin
thing => thing1
breadloaf => breadloaf
countertop => countertop
stool => stool
end
end))
4.4 What does forward planning look like?
ForwardPlan(world::ACSet, goal::ACSet, rules_dict::Dict, rule_limits::Dict, config::FFConfig)
Executes forward planning search to find a sequence or all sequences of applicable DPO rewriting rules. A sequence of applicable DPO rewriting rules that transform an initial state to a goal state is called a plan.function ForwardPlan(world::ACSet, goal::ACSet, rules_dict::Dict, rule_limits::Dict, config::FFConfig)
# Exit criteria: goal is reached
if homomorphism(goal, world, monic=true) !== nothing
println("Goal reached.")
return plan
end
applicable = find_applicable_rules(world, rules_dict)
# Backtrack criteria: no applicable rules
if length(applicable) <= 0
throw("No applicable rules found! Terminate path...")
end
try
for rule_hom in applicable # try all applicable rules in order
selected = rule_hom.first
# Backtrack criteria: rule applied too many times
try
if config.rule_usage[selected] >= rule_limits[selected]
println("Abort path. Rule used too many times.")
continue
end
catch
config.rule_usage[selected] = 1 # fails if key doesn't exist, initialize
end
# apply rule and add to plan
prev_world = world
try
world = rewrite(rules_dict[selected].rule, world)
catch e
throw("Could not apply rule! " * string(e))
end
append!(config.plan, [rules_dict[selected].rule => rule_hom.second]) # include both rule and matched homomorphism
try
config.num_step =+ 1
config.plan = ForwardPlan(world, goal, rules_dict, rule_limits, config)
return config.plan
catch e
world = prev_world
pop!(config.plan)
println("Path failed. Try a different path.")
# println(string(e))
end
end
catch e
throw("Something went wrong with error: " * string(e))
end
println("No plan found.")
end5.1 Future Work
5.1.1 Parameterize action models using constraints
Leverage composition to factor out applicability constraints and parameterize generic action models
5.1.2 Migrating plans from one domain (ontology) to another
Use functorial data migration (Spivak 2012) to translate actions to new domain ontologies
5.4 References
Agia, Christopher, Krishna Murthy Jatavallabhula, Mohamed Khodeir, Ondrej Miksik, Vibhav Vineet, Mustafa Mukadam, Liam Paull, and Florian Shkurti. 2021. “TASKOGRAPHY: Evaluating robot task planning over large 3D scene graphs.” 5th Conference on Robot Learning, 1–18. http://arxiv.org/abs/2207.05006.
Amiri, Saeid, Kishan Chandan, and Shiqi Zhang. 2022. “Reasoning with Scene Graphs for Robot Planning under Partial Observability.” IEEE Robotics and Automation Letters 7 (2): 5560–67. https://doi.org/10.1109/LRA.2022.3157567.
Galindo, Cipriano, Juan Antonio Fernández-Madrigal, Javier González, and Alessandro Saffiotti. 2008. “Robot task planning using semantic maps.” Robotics and Autonomous Systems 56 (11): 955–66. https://doi.org/10.1016/j.robot.2008.08.007.
Kolve, Eric, Roozbeh Mottaghi, Winson Han, Eli VanderBilt, Luca Weihs, Alvaro Herrasti, Matt Deitke, et al. 2017. “AI2-THOR: An Interactive 3D Environment for Visual AI,” 1–12. http://arxiv.org/abs/1712.05474.
Miao, Runqing, Qingxuan Jia, and Fuchun Sun. 2023. “Long-term robot manipulation task planning with scene graph and semantic knowledge.” Robotic Intelligence and Automation. https://doi.org/10.1108/ria-09-2022-0226.
Patterson, Evan. 2017. “Knowledge Representation in Bicategories of Relations.” CoRR abs/1706.00526. http://arxiv.org/abs/1706.00526.
Riehl, Emily. 2016. Category theory in context. http://www.math.jhu.edu/$\sim$eriehl/context/%0Ahttps://store.doverpublications.com/048680903x.html.
Spivak, David I. 2012. “Functorial data migration.” Information and Computation 217: 31–51. https://doi.org/10.1016/j.ic.2012.05.001.
Thiébaux, Sylvie, Jörg Hoffmann, and Bernhard Nebel. 2005. “In defense of PDDL axioms.” Artificial Intelligence 168 (1-2): 38–69. https://doi.org/10.1016/j.artint.2005.05.004.