PhD Thesis
Distributed trajectory generation for multiple autonomous vehicles using Bernstein polynomial-based methods
— 2023
Key information
Authors:
Supervisors:
Published in
July 20, 2023
Abstract
Esta tese apresenta uma metodologia eficiente e confiável para geração de trajetórias exequíveis seguras e livres de colisões para grupos de veículos autónomos e que satisfaz os requisitos temporais de aplicações de tempo real. A metodologia proposta visa abordar as seguintes questões- chave: (i) Satisfazer restrições que permitem evitar colisões em todas as instâncias de tempo de uma missão; A maioria dos métodos de geração de trajetórias existentes depende da discre- tização no tempo ou no espaço, o que faz com que só seja possível garantir que as restrições são satisfeitas entre os nós de discrctização empregando uma grelha de discretização fina. Em alternativa, parametrizam-se as trajetórias como curvas de Bézier e recorre-se ao método de relaxamento e refinamento de Bernstein para garantir que as restrições são satisfeitas em todos os instantes de tempo. (ii) Considerar o movimento rotacional de um drone para evitar problemas de exequibilidade para voos em espaços confinados; Para incorporar o movimento rotacional de um drone no problema, aproxima-se o corpo do drone por um elipsóide cujos eixos principais estão alinhados com os eixos da estrutura do corpo. O modelo elipsóide permite considerar explicitamente a orientação do drone e gerar trajetórias em ambientes com passagens estreitas. (iii) Desacoplar restrições para evitar colisões entre veículos e obter um esquema distribuído com baixas exigências de comunicação; Para aliviar a complexidade computacional de resolver o problema de forma centralizada, apresenta-se uma estratégia que permite gerar trajetórias de forma local e distribuída através da resolução de um problema de otimização de pequena escala que envolve apenas as variáveis individuais de cada veículo. Para garantir que as decisões locais satisfazem as restrições anti-colisão, adota-se a partição do espaço de Voronoi e força-se cada veículo a gerar a sua trajetória dentro da sua célula de Voronoi. A tese conclui com extensos resultados de simulação, envolvendo até 100 drones, que ilustram a eficácia da metodologia de geração de trajetórias proposta. This thesis presents an efficient and reliable trajectory generation framework that enables the computation of feasible, safe and collision-free trajectories for teams of autonomous vehicles while satisfying timing constraints imposed by real-time applications. The proposed framework aims to address a few key issues related to multi-vehicle trajectory generation: (i) Satisfying safety and collision-avoidance constraints at all time instances during a mission; Majority of the existing trajectory generation methods rely on discretization in time or space and, thus, ensuring that collision avoidance constraints are satisfied in between discretization nodes is only possible by employing a fine enough discretization grid. This, however, usually translates into a significantly large number of constraints that can hinder the application of these methods to real-time multi-vehicle trajectory generation scenarios. To avoid the complications associated with time gridding, we parameterize trajectories with B´ezier curves and propose the Bernstein relaxation and refinement method to guarantee that collision avoidance requirements are satisfied at any time instant, even for extended travel times. The proposed method exploits the unique properties of B´ezier curves to replace the infinitely many constraints in the problem with a finite set of constraints. The proposed method also enables a flexible trade-off between conservatism of the resulting set of constraints and computational complexity. (ii) Considering the rotational motion of a drone to avoid infeasibility problems with flights in tight spaces; To incorporate the rotational motion of a drone into the trajectory generation problem, in contrary to the commonly used sphere model, we approximate the drone body as an ellipsoid whose principal axes are aligned with the body frame axes. Although the symmetrical approximation of the vehicle’s body (with a disc or a sphere in 2D and 3D planning) results in straightforward construction of the configuration space, it is very conservative and fails to validate trajectories that are feasible upon considering the vehicle’s orientation. The ellipsoid model instead allows an explicit consideration of the drone’s shape and orientation which is necessary for trajectory generation in unstructured environments with narrow gaps and small spaces between obstacles. In order to derive constraints for collision avoidance between ellipsoid-shaped bodies we use the separating hyperplane theorem of convex sets. The resulting set of constraints is seamlessly integrated into the proposed Bernstein-based trajectory generation method. (iii) Decoupling inter-vehicle collision-avoidance constraints for a synchronous distributed scheme with low computation and communication demands; To alleviate the computational complexity of solving the problem centrally for a large group of vehicles, we present a scheme that enables local distributed trajectory generation by solving a small-scale optimization problem that only involves a vehicle’s individual variables. To ensure that local decisions satisfy the coupling collision avoidance constraints we adopt the Voronoi partitioning of space and enforce each vehicle to generate its trajectory inside (a subset of) its Voronoi cell towards the closest point (in the cell) to its goal position. A sequence of sub-problems are then solved in a receding-horizon manner, using only the relative position information exchanged between the neighboring agents, until the vehicles reach their goal positions. The set of local collision-avoidance constraints is derived taking into account the vehicle’s orientation in order to avoid infeasiblity issues with generating trajectories in tight spaces for hundreds of drones. Also, the resulting set of constraints can be evaluated with the proposed Bernstein relaxation method to ensure that safe separation criteria between trajectories are met at any time instant of the planning horizon. The thesis concludes with extensive simulation and experimental results, with up to 100 drone, to illustrate the efficacy of the proposed trajectory generation framework.
Publication details
Authors in the community:
Bahareh Sabetghadam
ist426951
Supervisors of this institution:
RENATES TID
101745656
Degree Name
Doutoramento em Engenharia Electrotécnica e de Computadores
Fields of Science and Technology (FOS)
electrical-engineering-electronic-engineering-information-engineering - Electrical engineering, electronic engineering, information engineering
Keywords
- Geração de Trajetórias
- Aplicações Multiveículo
- Curvas de Bézier
- Hiperplano de Separação
- Diagrama de Voronoi
- Trajectory Generation
- Multi-vehicle Applications
- Bézier Curve
- Separating Hyperplane
- Voronoi Diagram
Publication language (ISO code)
eng - English
Rights type:
Open access
Institution name
Instituto Superior Técnico