Estrategia de enrutamiento para la maniobra del enlace a un convoy de vehículos en entornos urbanos, robusta a la incertidumbre en los tiempos de recorrido

Resumo

This thesis proposes an optimal routing strategy for intelligent transport units moving autonomously in an urban scenario. Inside this scenario, defined by a set of streets and intersections (nodes), there is a group of independent mobile units carrying out specific tasks. On the other hand there is a peripheral road along which a convoy of vehicles is moving continuously. This convoy is composed by one leader and several followers, without mechanic link between them. The task of the convoy is to travel along the peripheral route linking all those transport units that can be required to carry out some specific task. A transport unit of the convoy might have to leave it at any time to perform a task, and once the mission is finished, return to the convoy as quickly as possible. This thesis focuses on providing solutions to the merging manoeuvre. In particular the return to the convoy of a single unit that has ended its mission. Taking into account that the movement of the convoy is restricted to the peripheral road, the meeting point amongst the convoy and any unit willing to return to it (pursuer), will be one of the peripheral nodes. On the other hand this meeting point must be selected in such a way that the link-up takes place in the shortest possible time, and the convoy always arrives at the meeting point after the pursuer. The first objective consisted on solving the merging manoeuvre when the travelling times along every street are considered well known and deterministic. In this case the problem is divided into two stages: a) development of an algorithm able to determine the optimal meeting point where the pursuer will merge the convoy and, b) decision of the best route (analysing the minimum number of nodes) from the current pursuer's position to the meeting point. It is important to highlight that the full search process happens very quickly and can be applied in real time. This has special interest on complex environments. The second goal consisted on extending our algorithms to a scenario where the times required to travel along the streets are not deterministic but random. This uncertainty is usual on real transport scenarios, and affects all the transport units. There are many sources of uncertainty, such as traffic density, weather conditions, hour of the day, etc. To model this uncertainty, we have used Gaussian probability distributions. This way the travelling times are now random variables characterized by a mean value and a variance. On the other hand, this non-deterministic behaviour prevents us from guaranteeing successful merging manoeuvres. Because of this, a novel parameter, named “Risk Factor”, limits the failure probability of the merging manoeuvre. This factor also influences the solutions that our algorithms achieve: in particular the time required for the manoeuvres, and the number of trajectory re-plannings that are necessary to carry out while the pursuer approaches the meeting point. The implementation of our proposal needs a remote centre with wireless connection with all transport units. The remote centre uses Dynamic Programming techniques, together with the information reported by the transport units, to keep updated relevant statistical values regarding the travelling times. The entire strategy was validated through different experiments, first on simulation and finally on real experiments. The Player/Stage tool allowed us to run simulated robots on a virtual map. The real experiments were carried out using P3-DX robots to perform the role of the leader and the pursuing unit.