Path planning of collaborative robots dealing with real maps and explicit time concerns

In the last decades robotic applications pervaded human life. Mobile plat forms, static manipulators, and mobile manipulators are increasingly used in our society to perform repetitive tasks. Robots side by side with human workers are deployed in every industrial eld, from mechanic, chemical and manufacturing industries, to transports of goods and people, to smart delivery systems and E-commerce. Thanks to their high flexibility, customizability and the possibility to nd on the market different products that are able to satisfy every customer's needs and requests, robots are selected for several purposes and employed in any possible working environment. For these reasons companies that rely on robotic applications for the ful lment of their tasks need programming tools that must handle their demand. For this motivation software programmers should guarantee programmable, reusable, flexible tools in order to cover all the aspects of all the possible ideas and needs of the customers which absolutely is not a trivial responsibility. The Co4robots project, within which this thesis has been developed, tries to overcome this issue. It aims at introducing software engineering principles and techniques within the robotic domain. The nal goal is shifting towards well-de ned engineering approaches which stimulate components reuse and have an impact on the robotic market-places. Co4robots assumes a robotic application composed by a set of robots (i.e., a team) that aim at performing a set of missions in a collaborative way. A mission is an high level goal that a robotic application must achieve. For example, a mission may require a team of robots to bring medical supplies to a surgery room in the hospital environment. Those missions are typically de fined in terms of a high-level complex mission - a formal description of the goals that robots shall achieve. Rather than developing the components of the system from scratch each time a new robotic application is designed, or missions are changed, Co4robots tries to develop systematic software engineering techniques for the development of robotic applications. These techniques include among others (i) new techniques that allow heterogeneous agents (including humans) to collaborate in manipulating and moving objects; (ii) decentralized real time planning algorithms that allows to synthesize the actions the robots in the team must perform; (iii) decentralized real-time perception to allow robots perceiving their environment either by using its own sensors or by exchanging sensory information with other nearby agents to accomplish speci c tasks; (iv) a software integration platform to enable easy deployment of robots which includes confi guration facilities. The platform aims at integrating the software produced within the project and drives the instantiation of the outcomes of research made into the project according to actual needs and (v) a user-friendly speci cation language that enables users (e.g., human users that utilize the robotic system in hand) without expertise in robotics and information technology (such as the personnel of a hotel or a hospital) to specify missions to be accomplished by the robots. Path planning is a key point in robotic industry, planning aims to compute a set of actions and movements that a robot or a team composed by several robots are supposed to perform in order to fulfi ll a desired mission. Motion planning has already been studied and analysed in literature. However, we believe that some of the needs of current robotic are still to be handled. In particular current robotics intrinsically ask for planner tools that possess the following features: (i) analyze missions which contain explicit time concerns; (ii) manage teams of robots; (iii) consider during the planning procedure how robots are able to perform actions and synchronize among each other; and (iv) work on realistic maps. At the moment, in literature contributions a planner presenting all this features integrated in one single tool is missing. This work proposes an approach that tries to solve all the problems described above. We present a motion planner that, in order to compute the commands to give to every agent of the team takes as inputs (i) the map of the environment in which the robots are deployed (in the format of images), (ii) the models of the robots that describe their possible movements, the actions they can perform, and how they synchronize, and (iii) a mission speci cation containing explicit time concerns. The approach takes as input a map describing the layout in which the robots will operate. A set of timed automata that describe the behavior of the robots. The mission the robot should achieve. The map of the environment is used to automatically generate a Timed Automaton (TA) that represents how robots can move within their environment. This TA is composed with other TAs that model how the robots behave. An high level mission describing the desired goal of the system (including explicit time concerns) is provided by the user as a Timed Computational Tree logic formula (TCTL). The Timed Automata model and the TCTL speci cation are given to the program Uppaal Model Checker which creates a trace (a plan) that if performed by the robots ensures the satisfaction of the mission of interest. This thesis has been evaluated under different aspects. We evaluated the proposing planning technique on realistic environments. In the tests performed we considered three real buildings, in particular: "Jupiter Building" of Chalmers University, Gothenburg, Sweden, "Edi cio20" and "Edi cio22" of Politecnico di Milano. The maps of this buildings have been transformed using two different encodings into a Timed Automata that describe the environment in which the robots are deployed. The two encodings have been evaluated considering several different missions. Each mission has been evaluated on different time intervals, which represent the maximum time available to execute the action. We test the reliability of the approach both on the simulator and on real scenarios. Regarding the simulated experiments we evaluated the generated traces by the planner on Choregraph software simulator. The simulator showed positive results regarding the applicability on real case scenarios. The real experiments were conducted in the "Jupiter Building" of Chalmers University and in the Pal Robotics Company (one of the partners of the project). In the experiments conducted in the `Jupiter Building" of Chalmers University, we considered the TurtleBot robot, a mobile platform able to move in narrow environments. We ask the TurtleBot robot to perform different missions: bring the coffee to the offices, perform security surveillance during the night and delivery objects in the building. In all the cases the approach successfully achieved its missions, (i) compute a plan from the map and the speci cation, (ii) deploy the right sequence of commands to the robot. In the experiments conducted in the Pal Robotics Company, we deployed our planner on the TIAGO Robot, a mobile platform of 145cm with a robotic arm. We considered different missions and a set of real case scenarios. The approach succeeded in all the experimental tests performed.

Negli ultimi anni le applicazioni robotiche sono diventate parte integrante delle nostre vite. Piattaforme mobili e manipolatori vengono sempre più utilizzati nella nostra società per eseguire azioni ripetitive, alienanti o pericolose per un essere umano. I robot, fianco a fi anco con i lavoratori, sono utilizzati in ogni settore industriale, dalla meccanica, alla chimica, al settore manifatturiero, per il trasporto di materiali e persone, per le consegne e per l'E-commerce. Grazie alla loro flessibilità, personalizzabilità e vasta gamma di scelta nel mercato globale, questo genere di prodotto è in grado di soddisfare ogni tipo di richiesta e bisogno del cliente. Per questo motivo le aziende che si affidano ad applicazioni robotiche necessitano strumenti di programmazione sempre aggiornati in modo da poter gestire le loro richieste e bisogni. Gli sviluppatori di software hanno il compito di garantire strumenti flessibili e riusabili in modo da compiere ogni necessità del consumatore. Il progetto Co4robots all'interno del quale questa tesi è stata sviluppata, ha l'obiettivo di fornire strumenti che agevolano la programmazione nel contesto di applicationi multi-robot. Co4robots mira ad introdurre nel campo della robotica principi e tecniche caratteristiche dell'ingegneria del software per fornire un approccio ingegneristico alla programmazione di applicazioni robotiche. Il progetto analizza principalmente applicazioni multi-robot nelle quali un team di robot collabora al fi ne di raggiungere il soddisfacimento di una data missione, che risulterebbe non eseguibile da un singolo robot. Per esempio, una missione potrebbe richiedere al team di robot di caricare e muovere oggetti o rifornimenti in un determinato ambiente, dagli uffici, alberghi agli ospedali e sale operatorie. L' obiettivo finale assegnato al team di robot è descritto e assegnato come una missione defi nita da un linguaggio di alto livello. Co4robots progetta di elaborare un approccio sistematico per lo sviluppo di applicazioni robotiche. Questo approccio include tecniche che riguardano diversi aspetti tra cui (i) la possibilità di lavorare con agenti eterogenei, tra cui lavoratori e supervisori, (ii) lo sviluppo di algoritmi per la computazione delle azioni che i vari agenti devono eseguire per raggiungere la missione assegnata, (iii) un controllo decentralizzato che permette ai robot di interagire con l'ambiente circostante attraverso l'utilizzo di sensori e la comunicazione tra i componenti del team, (iv) facile integrazione con i diversi sistemi presenti sul mercato, (v) l'utilizzo di un linguaggio di alto livello per la defi nizione delle missioni, in modo da non richiedere all'utente particolari nozioni di robotica. Questa tesi tratta uno dei vari aspetti considerati all'interno del progetto Co4robot: il planning. Il planning è un elemento fondamentale di ogni sistema robotico. Ha l'obiettivo di calcolare l'insieme di azioni e movimenti che il robot deve eseguire in modo da raggiungere l'obiettivo assegnato. Questo aspetto della robotica è già stato affrontato in letteratura, ma riteniamo che alcuni aspetti possano tuttavia essere approfonditi ed integrati. In particolare gli odierni strumenti per la pianifi cazione della traiettoria richiedono l'integrazione delle seguenti caratteristiche: (i) capacità di analizzare missioni che considerano aspetti temporali espliciti, per esempio missioni con vincoli espressi in secondi o minuti, (ii) abilità di gestire un team di robot composto da più agenti, (iii) considerare durante la piani cazione la possibilità di eseguire azioni collaborative che richiedono la sincronizzazione dei robot durante lo svolgimento della missione, (iv) considerare mappe realistiche che descrivono edifi ci ed ambienti reali. Al momento, in letteratura non è presente uno strumento che integra tutti questi aspetti in grado di supportare in modo efficace lo sviluppatore. Questo lavoro propone un approccio che mira a risolvere i problemi descritti. Viene presentato uno strumento per la pianifi cazione della traiettoria che, per calcolare i comandi da assegnare ai robot, analizza (i) la mappa, in formato di immagine, dell'ambiente in cui gli agenti andranno a lavorare, (ii) il modello dei robot che descrive le relative caratteristiche di movimento e azione, (iii) la missione che i robot hanno il compito di eseguire considerando aspetti temporali espliciti. Queste informazioni sono utilizzate per generare un modello del sistema che verrà utilizzato nella fase di planning. Il modello del sistema è composto dal modello dell'ambiente e dai modelli dei robot che compongono il team, e viene descritto mediante l'utilizzo di Automi Temporizzati. La missione assegnata al team di robot viene invece specifi cata come una formula espressa in linguaggio TCTL (Timed Computational Tree Logic) che è in grado di gestire aspetti temporali espliciti. Il modello descritto mediante gli Automi Temporizzati (che viene generato automaticamente) e la speci ca TCTL vengono processate da Uppaal, un software che, analizzando tali input, è in grado di verifi care l'esistenza di una sequenza di stati e transizioni in grado di soddisfare la missione. In caso di risposta affermativa la traccia viene analizzata e le azioni vengono assegnate ed eseguite dai vari robot nel team. La tesi è stata valutata sotto vari fronti. Abbiamo valutato il comportamento del planner considerando scenari realistici. Nei test eseguiti sono stati presi in considerazione 3 edifi ci, in particolare: "Jupiter Building", Chalmers University, Goteborg, Svezia, "Edi cio20" ed "Edi cio22", Politecnico di Milano. I piani di questi edifi ci sono stati mappati utilizzando due diversi encoding e diverse tipologie di missioni sono state valutate. Per ogni tipologia abbiamo considerato vari bound temporali, il cui valore rappresentava il tempo massimo ento il quale la missione doveva essere soddisfatta. L'algoritmo è risultato capace di computare un insieme di azioni e movimenti rappresentati per mezzo di una traccia che, se eseguite dai robot, garantiscono il soddisfacimento della missione di interesse. Per mostrare l'applicabilità dell'approccio in scenari realistici abbiamo prima di tutto valutato le tracce generate dal planner per mezzo del Choregraph Simulator. Il simulatore ha dimostrato la possibilità di eseguire le tracce su robot reali, e in particolare sul NaoRobot. Abbiamo quindi valutato l'utilizzo dell'approccio su delle applicazioni realistiche. Abbiamo considerato il Turtlebot, un robot mobile in grado di muoversi in spazi brevi e stretti, e considerato tre diverse missioni nelle quali il robot ha dovuto ritirare e consegnare il caffè, monitorare l'ingresso di personale non autorizzato ed eseguire il delivery di merce. In tutti i casi l'approccio è risultato capace di (i) computare un piano per il robot partendo dalla mappa e da una specifi ca contenente vincoli temporali (ii) eseguire un forwarding corretto delle azioni e dei movimenti al robot. Abbiamo quindi valutato l'utilizzo dell'approccio all'interno di Pal Robotics, uno dei partner del progetto. Abbiamo considerato il TIAGO Robot, una piattaforma mobile di 145 cm con un braccio robotico, e varie missioni provenienti da casi di studio reali. L'approccio è risultato efficace anche nel corso di questi esperimenti.