Roteamento dinâmico de veículos não-holonômicos para visita a regiões

Abstract

With the advance in the development and use of autonomous vehicles, it is necessary the development of techniques capable of generating efficient solutions to the many challenges related to the use of such vehicles. Among them, we can mention the use of vehicles with constrained motion (nonholonomic), visit to non-specific positions (regions), regions of interest determined dynamically over time and theuse of multiple vehicles. This work addresses the problem of efficient planning paths for a group of vehicles with movement restrictions, whose goal is to visit certain regions of interest dynamically determined in the environment. It is assumed that all vehicles are homogeneous and move with constant velocity. Therefore, the ultimate goal is to minimize the total time necessary to visit all regions. The first part addresses the problem by considering the case where only one vehicle is used. Based on certain characteristics observed in the best paths obtained from a proposed evolutionary algorithm, a deterministic heuristic is presented. Finally,we discuss the online strategy used to treat dynamic insertion of new regions to the path. Then, the proposed methodology is presented for the case with multiple vehicles. For the static case two methods are shown, the first one comprised the use of two existing techniques from the literature, and the second one is based on a memetic algorithm. Finally, all methods discussed are aggregated to a decentralized auction algorithm