Inertia-based Routing - New Approaches using Time-Optimal Trajectory Generation for Multirotor UAVs as an Example

Unmanned aerial vehicles (UAVs) are, from a physical point of view, inherently inert.
This means that they require an acceleration force to change their direction of movement
and/or velocity magnitude. Until now, however, these physical properties associated with
inertia have not been taken into account in the planning of a flight mission for a multirotor
UAV in sufficient detail. In the best case, this leads to the problem that the resulting
flight mission is not as efficient as the kinematic characteristics would allow. In the worst
case, the calculated mission plan requires physical properties such as maneuverability or
acceleration power that the considered multirotor UAV does not provide. Consequently,
the determined reference trajectory of the planned mission cannot be tracked by the UAV.
This results in spatial and temporal errors compared to what was planned which might
lead to a mission execution with a significantly lower quality than expected.
In this work, we give deep insights into the problem of inertia-based route planning with
multirotor UAVs, a special UAV type, as an example. To model the real physical capabilities
... mehr
of multirotor UAVs, we develop a new analytical approach for time-optimal trajectory
planning for point-masses with constrained velocity and acceleration. The trajectories
yielded by our new method have proven to be sufficiently precise in modeling a multirotor
UAV’s full physical capabilities. Further, since our approach is based on analytical solutions
in closed form, it is computationally extremely cheap.
Next, we introduce the kinematic traveling salesman problem (KTSP) and the kinematic
orienteering problem (KOP), which are based on the assumption that each waypoint
of a flight mission can be traversed with different heading angles and velocities. For
each possibility to travel between a waypoint pair, we utilize our time-optimal trajectory
planning approach introduced above to describe the associated motion. We develop a
mathematical model for both, the KTSP and the KOP, and hence can solve related problems
with a commercial general-purpose solver to global optimality. Since both problems are
combinatorial and classified as NP-hard, we additionally develop heuristic algorithms to
solve both problem classes in a short time with sufficient solution quality. The presented
results show that our research on inertia-based route planning problems significantly
improves the achieved quality of UAV mission planning compared to state-of-the-art
approaches.