Abstract
Traditional path-planning algorithms for Unmanned Aerial Vehicles (UAVs) often struggle in complex urban environments where geometric constraints are coupled with semantic restrictions, such as no-fly zones over water or private property. This paper presents a semantically extended Rapidly-exploring Random Tree (RRT) algorithm that integrates domain-specific ontologies to provide "common sense" reasoning during navigation. By leveraging the OntoCity ontology and a specialized PathConnection design pattern, the proposed system identifies functional alternatives to forbidden zones—such as using a bridge to cross a restricted river. Experimental results in Stockholm demonstrate a significant increase in path-finding success rates from 24.2% to 91%, with a 12-fold reduction in execution time.
Introduction
Navigating a UAV through a dense urban environment is a high-stakes challenge. Standard path-planning algorithms, such as RRT, operate by randomly sampling points in space to construct a path. However, these algorithms are typically "blind" to the semantic context of the environment. In cities like Stockholm, characterized by numerous islands and waterways, large areas may be designated as no-fly zones for safety or privacy. A standard RRT algorithm often fails in these scenarios because it spends excessive computational resources sampling invalid points within forbidden zones, failing to find narrow valid corridors like bridges.
System Architecture and Methodology
The proposed solution combines traditional geometric path planning with a formal semantic framework. The system architecture consists of several integrated components that transform raw satellite data into actionable navigation paths.
The workflow begins with high-resolution satellite imagery processed via a CNN-based classifier to generate an enriched labeled map. These labels (e.g., buildings, water, roads) are then used to populate the OntoCity ontology, a geo-representation model based on GeoSPARQL.
Semantic Knowledge Representation
The core innovation of this work is the PathConnection Design Pattern, which utilizes n-ary relations to describe the functional connectivity between urban regions.
When the RRT algorithm samples a point within a forbidden zone (e.g., a ontocity:River), the system triggers a Description Logic (DL) query. Rather than simply discarding the sample, the reasoner identifies an alternative region that fulfills the same functional role—connecting the same ontocity:Shore regions—but is legally flyable, such as a ontocity:Bridge. The planner then replaces the invalid sample with a valid one from the suggested alternative, effectively guiding the search toward viable corridors.
Experimental Results
The approach was evaluated using a dataset of Stockholm's central district provided by Vricon. The researchers tested the algorithm across 70 distinct path-finding problems with a 10-second execution limit. The improvement was dramatic:
| Metric | Standard RRT | Semantically Extended RRT |
|---|---|---|
| Success Rate | 24.2% | 91% |
| Avg. Execution Time | 8.4 seconds | 0.68 seconds |
The integration of semantic hints allowed the planner to find valid paths over 12 times faster than the baseline, significantly improving reliability in highly constrained environments.
Conclusion and Future Work
By prioritizing context over pure geometry, the semantically extended RRT enables UAVs to navigate with an awareness of social and legal constraints. While the current system excels at finding valid paths, future work will focus on path optimization to ensure the shortest possible routes. Additionally, the researchers aim to extend the ontology to handle dynamic constraints, such as temporary no-fly zones or changing weather conditions.
Summary updated