Near time-optimal trajectory optimisation for drones in last-mile delivery using spatial reformulation approach

Abstract

Seeking a computationally efficient and time-optimal trajectory for drones is crucial for saving time and energy costs, especially in the field of drone parcel delivery. Still, last-mile drone delivery is a challenge in urban environments, due to the existence of complex spatial constraints arising from high-rise buildings and the inherent non-linearity of the system dynamics. This paper presents a three-stage method to address the trajectory optimisation problem in a constrained environment. First, the kinematics and dynamics of the quadcopter are reformulated in terms of spatial coordinates, which enables the explicit evaluation of the progress of the path. Second, an efficient flight corridor generation algorithm is presented based on the transverse coordinates of the spatial reformulation. Third, the nonlinear model predictive control (NMPC)-based optimal control problem with obstacle avoidance is formulated for solving the time-optimal trajectory. Compared to the true time-optimal trajectory, the flight time of the near time-optimal trajectory is 3.10% longer than the true time-optimal trajectory, but with a 92.5% reduction in computation time. Numerical simulations based on an illustrative scenario as well as a real-world urban environment are conducted. Results demonstrate the effectiveness of the proposed method in generating near time-optimal trajectory but with a reduced computational burden.