Time-efficient path planning in a human crowded environment

This thesis focuses on the navigation of an autonomous mobile robot. In particular, the main goal is to develop a collision-free and time-efficient, optimal, path planning solution for the mobile robot in a human crowded environment by taking into account the possible future trajectories of the people. In this work, the adopted strategy for path planning relies on using a sampling-based replanning algorithm that dynamically updates the path in order to react to the unexpected movements of dynamic obstacles. In particular, the path planning method is based on the recent replanning algorithm, called RRTX, which is an asymptotically optimal sampling-based algorithm, that creates a tree rooted at the goal state, containing the lowest cost-to-goal information for the edges that are likely to be part of the optimal path solution. Also, this algorithm continuously updates the path during execution by instantaneously repairing and remodeling the tree in the environments whenever dynamic obstacles obstruct the optimal path of the robot. The second strategy adopted in this work is to introduce a human motion model which is based on a stochastic model that represents the uncertainty in the future motion of the people. In fact, the motion model probabilistically predicts the future trajectory of the people in order to prevent collisions in the area where the people are likely to be in the near future. Then, in order to integrate the people model into the path planning, we have employed a method such that the probabilistic results of the motion model are set as the weight terms to increase the cost of the RRTX nodes in the regions where there is likely to be a collision between the people and the robot. Thus, the robot tends to avoid these regions because of the increased cost and follows the optimal (the cheapest cost) path in the unobstructed regions of the environment. The performance of the path planning algorithm proposed in this thesis and RRTX algorithm has been evaluated by means of simulations including the people whose positions are taken from the real world. The simulation results have proved that the robot implemented with the proposed algorithm has shown a more natural behavior and a more stable movement with respect to RRTX algorithm.

Questa tesi riguarda la navigazione di robot che si muovono autonomamente. In particolare, lo scopo principale è lo sviluppo di un metodo di pianificazione di un percorso senza collisioni ed efficiente in termini di tempo, ottimale per un mobile-robot autonomo in un ambiente pieno di persone, delle cui future direzioni bisogna tener conto. Pertanto, la strategia adottata per la pianificazione del percorso si fonda sull'utilizzo di un algoritmo di ripianificazione basato sul campionamento che aggiorna dinamicamente il percorso in risposta ai movimenti imprevisti di ostacoli dinamici. In particolare, il metodo di pianificazione del percorso impiegato in questa ricerca si basa sul recente algoritmo di ripianificazione, chiamato RRTX, che è un algoritmo basato sul campionamento asintoticamente ottimale, e crea un albero di percorso ottimale che si origina dal goal state e si basa sul principio del minor cost-to-goal per i percorsi che probabilmente faranno parte della soluzione di percorso ottimale. Inoltre, questo algoritmo aggiorna continuamente il percorso durante l'esecuzione ricalcolando e rimodellando istantaneamente l'albero del percorso ottimale negli ambienti ogni volta che un ostacolo dinamico ostruisce il percorso ottimale del robot. La seconda strategia esaminata in questa ricerca è quella di introdurre un modello di movimento umano adottando un approccio stocastico che rappresenti l'incertezza nel movimento futuro delle persone. Infatti, il modello di movimento prevede probabilisticamente la traiettoria futura delle persone al fine di prevenire le collisioni nell'area in cui è probabile che le persone si trovino nel prossimo futuro. Quindi, al fine di integrare le persone con il modello nella pianificazione del percorso, si é adottato un metodo tale che i risultati probabilistici del modello di movimento siano impostati come termini di peso per aumentare il costo dei nodi RRTX nelle regioni in cui si rischia di avere una collisione tra i pedoni e il robot. Pertanto, il robot tende a evitare di trovarsi in queste aree a causa dell'aumento dei costi e segue il percorso ottimale (più economico) nelle regioni non ostruite dell'ambiente. Le prestazioni dell'algoritmo di pianificazione del percorso proposto in questa tesi e l'algoritmo RRTX sono state valutate sulla base di simulazioni che includessero delle posizioni di persone prese dal mondo reale. I risultati della simulazione hanno dimostrato che il robot implementato con l'algoritmo proposto ha mostrato un comportamento più naturale e un movimento più stabile rispetto all'algoritmo RRTX.