In this paper we propose an ontology pattern that represents paths in a geo-representation model to be used in an aerial path planning processes. This pattern provides semantics related to constraints (i.e., ight forbidden zones) in a path planning problem in order to generate collision free paths. Our proposed approach has been applied on an ontology containing geo-regions extracted from satellite imagery data from a large urban city as an illustrative example.
Path planning for unmanned aerial vehicles (UAVs) in urban environments is
becoming of increasing importance as the usage of drones is increasing both for
recreation as well as urban monitoring. Aerial path planners would have the
potential to provide greater safety for operating these vehicles, especially when
the line of sight for operators is not always available, or there are limitations
in real-time feedback. For such path planners, ight elevation is a critical
parameter, which depending on the scenario, can have varying requirements [
In this paper we exploit semantic information available in satellite images of urban maps in order to contribute in path nding and planning process for UAVs. Further and how they a ect the complexity of a path planning process. Although a precise answer to this question depends on many factors including the planning method, we focus on those set of problems where the constraints increase the searching time and consequently the complexity of the path nding process. More speci cally, in this paper, we show how exploiting the semantics of constraints given in a path planning problem can improve the time complexity of the planning process, which otherwise could be undesirably high.
Enabling path planners with semantics is not novel and has been studied
in the literature. Many of the studies are targeting indoor environments where
the semantic representation of the given objects either helps to interact with
humans [
Figure. 1 illustrates the main structure of our system including a path
planner enabled with semantics to better function in outdoor environments. As
mentioned earlier, we use satellite images of urban maps (in this paper, the central
part of Stockholm) provided by Vricon [
Let X Rd (d 2 N, d 2) be a d-dimensional con guration space whose
members indicate all the states of a vehicle or a robot's body in terms of its joint
angles. Let Xobs and Xfree also represent the obstacles and obstacle-free space,
respectively, where: Xfree = X n Xobs. Assuming that the initial condition xinit 2
Xfree and Xgoal Xfree, a path planning problem is de ned as a triplet (Xfree,
xinit, Xgoal) [
A sampling-based path planner relies on generating a tree whose nodes represent
samples that are randomly selected from a given con guration space X. The
construction process of the tree continues until either a feasible path from a given
xinit to a given goal is found or the searching time expires [
Algorithm 1 shows how the RRT random tree T rooted at the initial sample
xinit is built [
Algorithm 1 RRT Tree Construction
In case of an UAV, obstacles are understood as either elevation constraints or semantics constraints. In this paper, our goal is to show how using the semantics we can update the con guration space X and therefore reduce the time required for a collision-free path searching process. For the sake of simplicity, we consider a simple drone with 1-dimensional con guration, where each single con guration is represented as a 3D point in the space. In this case, the con guration space X is represented in 3D, where x, y and z coordinates are limited within a speci c numeric range depending on the width, length and height size of the environment. 3
Each labeled segment generated by the data classi er is represented in our
ontology called OntoCity (see Fig 1). The OntoCity ontology relies on GeoSPARQL
proposed by OGC as a standard vocabulary for geospatial data in RDF that
enables qualitative spatial reasoning upon this type of data [
Although OntoCity extends the GeoSPARQL ontology by providing a taxonomy of geo-related concepts, it requires further semantics to contribute in path planning processes. In OntoCity, there is a representation of transportation routes in the form of the class ontocity:Way whose subclasses are ontocity:Road, ontocity:Street, ontocity:River, etc. To provide further details (e.g., the regions connected to the route) an extension is required. Representation of a path with its involved regions asks for a relation that is de ned between more than two elements. More speci cally, a path is seen as an n-ary relation semantics that can be represented via the generic n-ary1 ontology pattern.
However, the n-ary path relation in our case is a symmetric n-ary (SNAry)
relation. According to [
IndirectNeighbors v = 2 hasRegion:ontocity:Region
= 1 hasP ath:ontocity:Way
There are also two object properties, hasPath, connects and hasRegion with the following de nitions that indicates their domain and range classes: > v 8 hasP ath :PathConnection ;> v 8 connects :PathConnection ;> v 8 hasRegion :IndirectNeighbors > v 8 hasP ath:ontocity:Way ;> v 8 connects:IndirectNeighbors ;> v 8 hasRegion:ontocity:Region 1 https://www.w3.org/TR/swbp-n-aryRelations/
By specializing the classes of the pattern, the ontology will contain more speci c path connections. For instance, as shown in Fig. 3, the class PathConnection as the main class of the pattern subsumes the class RiverConnection whose path and region parts are de ned as the subclasses of the class ontocity:River v ontocity:Way and the class ontocity:Shore v ontocity:Region , respectively: where :
and; where :
= 1 hasP ath:ontocity:River
= 2 hasRegion:ontocity:Shore ontocity:Shore v ontocity:GroundArea v ontocity:Region
= 1 hasP ath:ontocity:Bridge ontocity:Bridge v ontocity:Way v ontocity:Region
Likewise, the class BridgeConnection is another specialization of the class PathConnection that de nes bridges as paths over water areas as follows:
Although path connections are de ned as the sibling classes, they can be further related to each other due to the similarities that might exist in their types of regions or ways involved in their de nitions. For instance, the two classes BridgeConnection and RiverConnection are similar in the sense that both connect shore areas. Finding these similarities might help a path planner to nd better candidates or substitutes for the areas expected to be avoided. 3.2
Given the populated ontology with all the regions and their connections, the system is asked to nd an aerial path between two regions without passing upon a speci c region type C as a constraint. Assuming this region type is de ned in the ontology, C v ontocity:Region , the following query given in DL-query syntax let the reasoner retrieve all the candidates of the region type C that are although di erent from C (and therefore legal for the sampling process of the path planner), they are similar to C in the sense that they play the same role as C in connecting speci c region types: ontocity:Region and (not C) and inverse hasP ath some ( connects some ( inverse connects some (
hasP ath some C)))
This query is executed by the path planner during the tree construction process explained in Algorithm 1. In other words, involving the query process to the path planning algorithm results in adding extra steps between line 4 and 5. This extension has been shown in Algorithm 2 in red. Each time a random sample is fetched (line 4), the planner checks if it belongs the forbidden area C (line 5). If it is the case, the selected xrand has to be replaced by a new sample taken from the alternative region Ralt retrieved by the reasoner as the result of the query.
Algorithm 2 Semantically Extended RRT Tree Construction 1: T .init(xinit) 2: for i = 1 to k do 3: G.add(xinit) 4: xrand RAN D CON F () 5: if xrand 2 C then 6: Ralt QU ERY P AT T ERN (C) 7: xrand RAN D CON F (Ralt) 8: end if 9: xnear N EAREST V ERT EX(xrand; T ) 10: xnew N EW CON F (xnear) 11: T :addvertex(xnew) 12: T :addedge(xnear; xnew) 13: end for 14: return T
Although the regions retrieved by the running the query upon the ontology are authorized regions and therefore are considered as part of the Xfree space of the path planner, it is worth nding these regions in order to emphasize on their existence and increase their chance to be chosen within the sampling phase. More speci cally, without emphasizing on these alternative paths, there is the risk of not nding a path when the majority of the area is covered by the forbidden region C. One may pose the question: why before running the sampling process, we do not exclude all the forbidden regions from the con guration space. The answer is that depending on type, size, number and the geometry of constraints (i.e., forbidden zones) this process can become highly time consuming. Furthermore, regardless of the location of forbidden zones, we have to always exclude them from the con guration space. However, in our suggested approach we apply the reasoner only if an invalid sample is selected, which is perhaps compensated by an admissible alternative. 4
Using the populated OntoCity, the RRT path planner considers regions as obstacles. Each obstacle is represented in the form of a vertical 3D box whose base and height are equivalent to the bounding box of the region's boundary and the elevation average of the region, respectively. As shown in Fig. 1, the user is able to choose an initial and a goal point by clicking on the 3D map provided by the visualizer and asks for a collision free path. He/she can also mention speci c region types as the constraints (i.e., forbidden zones) of the path nding problem.
However, avoiding regions due to their type or label is not always straightforward. Since the sampling based path planners are in theory incomplete, if the area is highly constrained, the process of nding valid samples and subsequently a collision free path (in terms of constraint satisfaction) is prone to fail. To illustrate, we use water as a constraint in the central part of Stockholm which is made of up of a number of islands. Given the water area as a constraint (C = ontocity:WaterArea ), the process of nding a path between two points located at two di erent sides of water will have a chance to successfully nish only if the sampling process takes advantage of the context of the scenario and samples from the bridges whose areas' size is unfortunately much smaller than the size of the environment.
As explained in Section 3.1, our solution to this problem is to apply the extended RRT Algorithm 2 according to which, once a sample is taken from a forbidden area (xrand 2 C), the reasoner runs the following query upon the ontology to nd a substitute region (Ralt) for water areas connecting two shores: Region and (not W aterArea) and inverse hasP ath some ( connects some ( inverse connects some (
hasP ath some W aterArea)))
Due to the given constraint, all the regions which are the instances of the subclasses of the class ontocity:WaterArea v Region (e.g., rivers) are seen as constraints. Given the forbidden region types in the form of constraints, the reasoner will retrieve all the connections (i.e., instances of the PathConnection class) whose path (i.e., a subclass of the class ontocity:Way ) refers to the instances of these regions. The reasoner can also nd the types of regions (i.e., indirect neighbors) connected via a forbidden region (e.g., a river). Knowing these neighbors, the reasoner will be able to retrieve an alternative region (Ralt) which is similarly connecting the neighbor regions in order to emphasize them during the sampling process (xrand 2 Ralt). (a) Constraint: Elevation of regions (b) Constraint: Water Areas. Invalid and alternative samples are in orange and pink, respectively.
Figure 4(a) shows a path that connects two points (xinit in red and xgoalingreen) by crossing the river. Given water areas as forbidden zones, the planner would have di culties in nding a path as the majority of samples are located in water areas due to their bigger area size. However, as depicted in Fig. 4(b), the path planner constructing the tree according to Algorithm 2, replaces samples taken from the river (xrand in orange) with new samples taken from the bridge as an alternative (xalt in pink) for the class ontocity:River .
We have run the algorithm for 70 di erent path problems with di erent initial and goal points located in the central part of Stockholm. Table 1 shows the success rates with and without using the ontology reasoning during the tree construction process of the planner. As we can see, the integration of semantics into the plan generation process increases the success rates from 24.2% (17 successful cases out of 70) to 91% (64 successful cases out of 70) within 10 seconds set as the time limit for path nding. Without using the ontology, the average time for generating a path approaches the set upper limit of the planning process. 5
In this paper, we explained our preliminary work on enabling RRT path planner with semantics to deal with the planning time complexity in highly constrained environments. We have proposed an ontology pattern to model path connections in the form of an n-ary relation. We also showed how involving the semantics of constraints can contribute in decreasing the time of a path nding process. Although in order to achieve such an improvement we need to rst populate the ontology with all the path connections between regions, this population process needs to be done only once. It is worth mentioning that in this work, we were only concern about path nding regardless of the length of the paths. As the next step, we will target path optimization with semantics as our objective function. Acknowledgments. This work has been supported by the Swedish Knowledge Foundation under the research pro le on Semantic Robots, contract number 20140033.