Couverture Convexe Optimale comme Approximatif d'Espace sans Collision pour la Génération de Trajectoires

Nous proposons un algorithme itératif en ligne pour trouver une couverture convexe appropriée afin de sous-approximater l'espace libre pour la navigation autonome afin de délimiter les Couloirs de Vol Sécurisés (SFC). La couverture convexe consiste en un ensemble de polytopes tels que l'union des polytopes représente un espace sans obstacle, nous permettant de trouver des trajectoires pour les robots qui se situent à l'intérieur de la couverture convexe. Afin de trouver les SFC qui facilitent la génération optimale de trajectoires, nous trouvons de manière itérative des polytopes se chevauchant d'un volume maximal qui incluent des points de passage spécifiés initialisés par un planificateur géométrique ou cinématique. Les contraintes aux points de passage apparaissent dans deux phases alternées d'un problème d'optimisation conjoint, qui est résolu par une méthode inspirée de la Méthode des Directions Alternées des Multiplicateurs (ADMM) avec des variables partiellement distribuées. Nous validons l'efficacité de notre algorithme proposé en utilisant une gamme d'environnements paramétrés et montrons ses applications pour la planification de mouvement en deux étapes.