In this paper, we provide an ontological analysis of the implicit assumptions within the specification of robot path planning problems. We propose a set of ontologies for representing spatiotemporal entities and relations that formalize the fundamental ontological commitments of path planning. One of the ultimate goals of autonomous robots is that robots can perform tasks without being instructed on how to do them. In other words, robots must be able to plan their own paths, which means constructing a collision-free path from a start to a goal position in the specified physical space. Such a problem is often considered to be low-level motion planning that computes the actual movements the robot should carry out [1]. Therefore, the robots must be given a complete description of the spatial environment including the location of spatial entities and their relations in the domain. Representing such domain knowledge is crucial for a robot to perform tasks efcfiiently and effectively. Ontology-based knowledge Representation and Reasoning (KR) provides a structured framework to represent and reason about the environment, enabling autonomous robots to perceive their surroundings in a more comprehensive manner. By incorporating ontological models into computational motion planning algorithms, robots can leverage the rich semantics associated with the objects, their properties, and relationships to make more informed decisions and generate context-aware paths. Based on the definition by Bloisi [ 2] the context knowledge of robots includes not only static knowledge, such as common sense, but also dynamic knowledge that has high time dependency due to continuous changes in real-time. Traditionally, algorithms of path planning problems are situated within a static environment in which only spatial information is needed (e.g., known obstacles and free spaces). Meanwhile, previous approaches used to define robotics relation ontologies often distinguish spatial and temporal KR in the planning process, where planning with time constraints and planning with geometric constraints are separate phases[1]. However, temporal constraints often need to be considered with the dynamics of the real-world environment
such as collision and interaction with other moving objects. For example, thinking about a simple path planning problem:
Given a room with a set of moving objects, find a path the robot can take from one location to another, avoiding contact with any objects.
In this case, both spatial and temporal constraints must be considered as obviously no two solid objects can be located at the same location at the same time otherwise a collision will occur. In this study, we focus on the representation of the contextual knowledge environment, and in particular, on the location and temporal information of moving robots and objects in a specified environment. The major research question we explore in this study is: what is the minimum ontology we need to represent the spatial and temporal knowledge in the path planning problem? The rest of this paper is organized as follows: we first begin with an informal planning problem for robotics, and then we discuss some ontological analysis and commitments of path planning representations. Next, we introduce the ontologies we use for knowledge formalization and then present the formalization of path planning notions using these ontologies.
In this section, we present a scenario that can be used to determine the requirements of the ontology.
Autonomous robot waiters are used in the restaurant to deliver dishes from the kitchen to the severing tables. Robot waiter X is scheduled to pick up dishes in the kitchen, and then dock at table A, table B, and table D to serve the customers, and then return to the kitchen. When the robot is leaving Table B for Table D, another Robot Y is moving from Table D to C which blocks the path from Table B to Table D, so there is a potential collision if Robot X continues the scheduled plan.
In order to represent this scenario, the fundamental notions that we need are the location of the table and the path of the moving robots. In this context, the tables are considered to be static obstacles that are located in fixed spatial regions during the entire time. Meanwhile, the location of a moving robot changes as time changes, and such change can be treated as a motion activity, though it is not explicitly expressed in natural language. The location change also causes a change in the spatial relations between robots and tables (e.g. the potential collision). Thus, we need an ontology for integrated knowledge about space and time rather than space alone, and to represent the change in time of spatial relations and the continuity of spatial location change. This leads to four main competency questions for the ontology development: • What is the relation between a static physical object and its located region (obstacle region)? • What is a moving path? • What is the relation between a moving object (motion activity/event) and its moving path? • What relations or constraints are held between two moving paths? e.g collisions The aforementioned scenario and competency questions are used throughout the paper to evaluate the existing work and address the need for the ontology for path planning.
Spatial and temporal KR are two fundamental knowledge representations and reasoning
techniques. Spatial KR provides generic knowledge about entities and their spatial relations in the
environment. Temporal KR is used to represent time information which includes the ordering and
sequencing information for tasks, resources, etc. Studies over the past decades have established
a solid foundation of formal ontologies of both space and time. Region Connection Calculus
(RCC), particularly RCC-8, is the most popular theory of spatial reasoning embodying both
mereological and topological aspects [
Material objects and events are two foundational topics in philosophy and ontologies. Arguments
on the differences between objects and events are commonplace in literature. Material objects,
such as stones, are said to exist, yet events are neither substances nor do they exist, and instead, the
“being” of events is to take place or occur [
Typically, robotic path planning is split into two components - task and motion planning. Task
planning occurs at a higher abstraction level, with additional information provided beyond
geometric data. Motion planning occurs at the geometric level - environments are broken down
into arbitrary cells as the environment model, and the optimal path is derived through classical
algorithms such as rapidly-exploring random trees (RRT). Recent work has sought to combine
these two components in a bid to exert more semantic control over the geometric path planning
process. The goal is to use ontologies as semantic control that prunes the search space for
the path planning process, hence allowing continuous interaction to be viable even in highly
complex dynamic environments (rich in state-changing obstacles), without utilizing large amounts
of computational power [
The ontological commitments are driven by the semantic requirements and competency questions extracted from the motivating scenario. The fundamental notions we need are the formal representations of obstacle regions and moving paths as well as how they interact with robots and other physical objects in a specified environment.
Substantivalists believe that entities are located at regions of space or spacetime, as opposed to
the supersubstantival view in which located entities are identical to their locations [
Meanwhile, we can also make the following definition of obstacle regions: 2. An obstacle region is a spatial region that is occupied by static objects or their parts in a specified environment.
A moving path of a robot notes the change of the location of the robot as time changes. Thus, in order to take temporal knowledge into account, we treat the moving path as spatiotemporal regions where space and time are combined as one primitive domain instead of two separate ones. As discussed in the previous section, entities are distinct from their located regions; therefore, a moving object (motion activity) should also be distinct from the spatiotemporal region it occupies, and events and space-time maintain their own mereotopologies. We also believe that there is a spatiotemporal analogy between the moving path of a robot’s motion and the spatial occupying relation between a static object and the obstacle region. Thus, we make the following commitments on the robot’s motion and its moving path: 3. A moving robot (motion) is disjoint from its moving path.
4. A moving path is a spatiotemporal region that is occupied by a robot’s motion activity.
The execution plan of a robot is highly dependent on task constraints, including time constraints, location constraints, etc. For example, the planned moving path of a robot cannot overlap with the obstacle region, nor can it intersect with another moving object’s path. In other words, we want to explore what relations or constraints need to be held between moving paths and obstacle regions. Here we present some basic constraints: 5. A moving path cannot spatially overlap with obstacle regions. 6. A moving path cannot spatiotemporally overlap with another path. 7. All parts of a robot’s moving path are ordered in time, and these parts must be connected spatiotemporally.
It is obvious that no two objects can occupy the same spatial region at the same time; otherwise, a collision will occur. Since we define the moving path as a spatiotemporal region, for any spatiotemporal region that is occupied by a motion, its corresponding spatial region should not overlap with obstacle regions(e.g. a moving robot and a table). Meanwhile, at any time t, the corresponding spatial regions of two moving paths should not overlap with each other. It is very common that a robot’s task consists of multiple sub-tasks, and the robot may stop moving at some point and resume multiple times; therefore, a robot’s moving path (a spatiotemporal region) can also be decomposed into multiple parts which are also spatiotemporal regions. It is obvious that these parts must connect to each other, and there exists a sum of these segmented spatiotemporal regions, which is the whole moving path of the robot. For example, a server robot moves from table A to B, docks at B, and continues moving from table B to D is a complex activity that occupies a complex spatiotemporal region ST. This activity can be decomposed into three subactivities which are moving from table A to B, docking at B, and moving from table B to D. Each subactivity also occupies a spatiotemporal region that is part of the complex spatiotemporal region ST. The corresponding parts(sub-spatiotemporal regions) must connect to each other, and their mereological sum is ST.
Based on our commitments, we combine a spatiotemporal ontology and a location ontology together to represent the basic notions of the path planning problem.
In our previous research, we developed a new spatiotemporal ontology based on the
mereotopology of RCC8 and Allen’s time algebra [
One fundamental issue to address for robot path planning KR is what is the relation between
moving objects and their moving paths, and how such relation interacts with obstacle regions
in a physical environment. As we discussed earlier in Section 2, objects’ movements can be
treated as events or activities; thus, the relation between moving objects and moving paths can
be viewed as the locations of motion activities. Our previous study on the location ontology
for events integrated an activity ontology - Process Specification Language (PSL)[
Here we present the formalization of our ontological commitments discussed in Section 4 using the spatiotemporal and event location ontologies. The major signatures and the relations we used are listed in Table 1.
First, we define motion activity in the context of robot path planning. When an object changes
its location(the spatial region that the object occupies), there is an occurrence of motion activity.
In order to represent change in location, we use the methodology of [
∀(a)motion(a) ≡ ∀ (o, x)occurence_o f (o, a) ∧ participates_in(x, o) ∧prior(loc(x, r1), o) ⊃ holds(loc(x, r2), 0) ∧ (r1 ̸= r2) (1) Next, we formalize the commitments we made in Section 4. Equation (2)&(3) are the formalization of Commitments 1&2 respectively. Commitment 3&4 are corresponding to Equation 4. Commitment 5-7 are formalized by Equation 5-7.
∀(x, y)occupies(x, y) ⊃ physical_body(x) ∧ region(y) ∀(r)obstacle_region(r) ≡ ∃ (x, y)static_physical_body(x) ∧ occupies(x, y)
∧spatial_part(r, y) ∀(p)path(p) ≡ ∃ (o)occurence_o f (o, motion) ∧ st_occupies(o, p) ∀(p, r1,t)path(p) ∧ pro jectsTo(p, r,t) ⊃ ¬∃ (r2)obstacle_region(r2) ∧ overlaps(r1, r2) (5) ∀(x, y)collision(x, y) ≡ ∃ (p1, p2)occurence_o f (x, motion) ∧ occurence_o f (y, motion) ∧st_occupies(x, p1) ∧ st_occupies(y, p2) ∧ st_overlaps(p1, p2) ∀(o1, o2, o3, p1, p2, p3)occurence_o f (o1, motion) ∧ subactivity_occurence(o2, o1) ∧subactivity_occurence(o3, o1) ∧ st_occupies(o1, p1) ∧ st_occupies(o2, p2) ∧st_occupies(o3, p3) ∧ st_sum(p1, p2, p3) ⊃ st_C(p1, p2)
With axioms introduced in previous section, we can represent the motivating scenario described in Section 2. For example, the obstacle region can be inferred by the following formula: ∀(r)obstacle_region(r) ⊃ ∃ (ra, rb, rc, rd)occupies(TableA, ra) ∧occupies(TableB, rb) ∧ occupies(TableC, rc) ∧ occupies(TableD, rd)∧ (spatial_part(r, ra) ∨ spatial_part(r, ra) ∨ spatial_part(r, rb)
∨spatial_part(r, rb) ∨ spatial_part(r, rd)) We can also represent the collision using the following ground formula: occurrence_o f (occ1, motion) ∧ participates_in(RobotX , occ1) ∧occurrence_o f (occ2, motion) ∧ participates_in(RobotX , occ2)
∧collision(occ1, occ2)
This study set out to provide an ontological analysis of robot path planning problems based on the philosophical stance of space, time and events. We identify a motivating scenario to justify our ontological commitments and provide axiomatizations of some basic notions of robot path planning, including obstacle regions, robots’ moving paths, and collisions, using the spatiotemporal ontology and event location ontology from our previous studies. In this paper, we focus on a low-level planning issue that only involves basic spatial and temporal contextual knowledge. Thus, a natural progression of this work is to integrate task-related knowledge to represent higher-level planning and scheduling issues. (2) (3) (4) (6) (7) (8) (9) st_part(a, b) st_C(a, b) st_overlaps(a, b) st_sum(a, b, c) T _occupy
spatial_part(x, y) Tpsl spatial_C(x, y) occupies(x, y) activity(a) activity_occurrence(o) occurrence_o f (o, a) subactivity(a1, a2) subactivity_occurrence(o1, o2) holds( f , s) prior( f , s) T _st_occupies st_occupies(o, st) st is a spatiotemporal region spatiotemporal region st can be projected to a spatial region r at time t spatiotemporal region a is part of the spatiotemporal region b spatiotemporal region a is connected to the spatiotemporal region b spatiotemporal region a overlaps with the spatiotemporal region b the sum of spatiotemporal region a and the spatiotemporal region b is spatiotemporal region c the spatial region x is part of the spatial region y the spatial region x is connected to the spatial region y the physical body x occupies the spatial region y a is an activity o is an activity occurrence o is an occurrence of a a1 is a subactivity of a2 o1 is a subactivity occurrence of o2 the fluent f is true immediately after the activity occurrence s the fluent f is true immediately before the activity occurrence s an activity occurrence o occupies the spatiotemporal region st