<p>Path planning is a major problem in autonomous vehicles. In recent years, with the increase in applications of unmanned aerial vehicles (UAVs), one of the main challenges is path planning, particularly in adversarial environments. In this paper, we consider the problem of planning a collision-free path for a UAV in a polygonal domain from a source point to a target point. Based on the characteristics of UAVs, we assume two basic limitations on the generated paths: an upper bound on the turning angle at each turning point (maximum turning angle) and a lower bound on the distance between two consecutive turns (minimum route leg length). We describe an algorithm that runs in <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="500_2025_10481_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="80" /> </InlineMediaObject> <EquationSource Format="TEX">$O(n^2 \log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time and finds a feasible path in accordance with the above limitations, where <i>n</i> is the number of obstacle vertices. As shown by experiments, the output of the algorithm is much closer to the shortest path with this requirement (always below about 10% of the shortest path), in a much smaller time (up to 10,000 quicker, in our experiments). We further demonstrate how to decompose the algorithm into two phases, a preprocessing and a query phase. In this way, given a fixed start point and a set of obstacles, we can preprocess a data structure of size <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="500_2025_10481_Article_IEq2.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">$O(n^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> in <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="500_2025_10481_Article_IEq3.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="80" /> </InlineMediaObject> <EquationSource Format="TEX">$O(n^2 \log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time, such that for any query target point we can find a path with the given requirements in <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="500_2025_10481_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="73" /> </InlineMediaObject> <EquationSource Format="TEX">$O(n \log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time. Finally, we modify the algorithm to find a feasible (almost shortest) path that reaches the target point within a given range of directions.</p>

RCS: a fast path planning algorithm for unmanned aerial vehicles

期刊论文
发表日期：

2025年1月1日

查看全文

Mohammad Reza Ranjbar Divkoti,
Mostafa Nouri-Baygi

摘要

Path planning is a major problem in autonomous vehicles. In recent years, with the increase in applications of unmanned aerial vehicles (UAVs), one of the main challenges is path planning, particularly in adversarial environments. In this paper, we consider the problem of planning a collision-free path for a UAV in a polygonal domain from a source point to a target point. Based on the characteristics of UAVs, we assume two basic limitations on the generated paths: an upper bound on the turning angle at each turning point (maximum turning angle) and a lower bound on the distance between two consecutive turns (minimum route leg length). We describe an algorithm that runs in $O(n^2 \log n)$ $O (n^{2} log n)$ time and finds a feasible path in accordance with the above limitations, where n is the number of obstacle vertices. As shown by experiments, the output of the algorithm is much closer to the shortest path with this requirement (always below about 10% of the shortest path), in a much smaller time (up to 10,000 quicker, in our experiments). We further demonstrate how to decompose the algorithm into two phases, a preprocessing and a query phase. In this way, given a fixed start point and a set of obstacles, we can preprocess a data structure of size $O(n^2)$ $O (n^{2})$ in $O(n^2 \log n)$ $O (n^{2} log n)$ time, such that for any query target point we can find a path with the given requirements in $O(n \log n)$ $O (n log n)$ time. Finally, we modify the algorithm to find a feasible (almost shortest) path that reaches the target point within a given range of directions.