[en] Searching and tracking are important behaviours for a mobile service robot to assist people, to search-and-rescue and, in general, to locate mobile objects, animals or humans. Even though searching might be evident for humans, for robots it is not, since it requires exploring, handling noisy sensors, coping with dynamic obstacles, and coordination in the case of multiple agents. In this thesis, we present several methods to search and track a person in an urban environment. All methods were fist tested extensively in simulation and then in real-life, using one or two mobile service robots, called Tibi and Dabo. The robots have laser range finders, which are used to navigate, to detect obstacles and to detect people's legs. Since we focus on search-and-track methods, we use existing methods for robot navigation, for people detection and person recognition. First tests are done with the hide-and-seek problem, in which the robot learns to catch the hider. Concretely, a Mixed Observable Markov Decision Process (MOMDP) model is used, in which the seeker's location is fully observable and the hider's location partially observable. Since the computational complexity depends on the number of states, we propose a hierarchical on-line method that reduces the state space by grouping them together. Although the method worked properly in simulation, in the real-life experiments the results were not satisfying and the on-line policy calculation was not fast enough to work in real-time. To handle larger environments, work in continuous state space and run in real-time, we propose to use an approach, the Continuous Real-time POMCP (CR-POMCP), that does Monte-Carlo simulations to learn a policy. The method performed correctly in simulation, but on the real robot it resulted in slow zigzag movements. Therefore, a new method is proposed, which uses the highest probable locations, according to its probability map (belief). Since the belief propagation of the POMCP resembles how a Particle Filter (PF) works, we also propose a method that uses a PF to maintain the belief. The PF method has to handle lack of observations, therefore, we introduce a special weight function. Both belief update methods take into account sensor and actuator noise, false negative detections, false positive detections (for a short time) and dynamic obstacles. Finally, a cooperative distributed multi-agent method is presented, it makes use of the previous belief update functions, but it uses all the agents' observations. Next, the search locations are assigned by exploring the working environment, taking into account: the belief, the distance to the search location and if another agent already will search close to it. Summarizing, the main contributions of this thesis are several methods to search and track a person in an urban environment with one or more mobile service robots. All these methods have been shown to work through a set of simulations and real-life experiments.

[nl] Zoeken en traceren zijn belangrijke manieren om een mobiele servicerobot te helpen mensen, om te zoeken en te redden en, in het algemeen, om mobiele objecten, dieren of mensen te lokaliseren. En hoewel zoeken evident is voor de mens, is dit niet het geval voor robots. Het vereist namelijk verschillende vaardigeheden zoals verkennen, omgaan met ruis in de sensoren en dynamische obstakels en coördinatie in het geval van meerdere agenten. In deze thesis presenteren we verschillende methoden om een persoon te zoeken en te volgen (search-and-track) in een stedelijke omgeving. De methoden zijn eerst getest met simulaties en daarna met twee echte mobiele servicerobots, genaamd Tibi en Dabo. De robots hebben laser rangefinders om te navigeren en om obstakels en benen van mensen te detecteren. Omdat we ons richten op het zoeken en volgen van mensen gebruiken we bestaande methoden voor de robotnavigatie, detectie van personen en het herkennen van de gezochte persoon. De eerste testen gedaan met het spel hide-and-seek, waar de robot leert om de persoon te vinden. Een Mixed Observable Markov Decision Process (MOMDP) is gebruikt, waar de positie van de robot (zoeker) volledig waarneembaar is en die van de persoon (verstopper) gedeeltelijk. Omdat de berekeningscomplexiteit van het aantal staten afhangt, stellen we een hiërarchische online methode voor die de staatruimte verkleind door het groeperen van staten. Hoewel de methode goed werkt in simulatie, waren de resultaten van de experimenten met de robots minder goed. Verder was het online genereren van de politiek niet snel genoeg. Om in grote omgevingen te kunnen werken en continue staatruimte te gebruiken in real-time, hebben we de Continuous Real-time POMCP (CR-POMCP) voorgesteld. Dit algoritme gebruikt Monte-Carlo simulaties om de politiek (beste actie voor een bepaalde staat) te leren. De methode werkte goed in de simulaties, maar de robot maakte in de experimenten zigzaggende bewegingen. Om deze reden hebben we een nieuwe methode voorgesteld die gebruik maakt van een waarschijnlijkheidskaart (belief) over de lokatie van de persoon. Omdat de propagatie van de POMCP lijkt op hoe een Particle Filter (PF) werkt, stellen we ook een methode voor die een PF gebruikt om de belief bij te houden. De PF methode moet om kunnen gaan met missende observaties en we introduceren daarom een speciale gewichtsfunctie. Beide belief update methoden houden rekening met sensor en actuator ruis, incorrecte negatieve detecties, incorrecte positieve detecties (gedurende een korte tijd) en dynamische obstakels. Als laatst presenteren we een coöperatieve multi-agent methode die gebruik maakt van de genoemde belief update methoden, maar tevens gebruik maakt van de observaties van alle agenten. Vervolgens worden de zoeklocaties toegekend om de hele omgeving te verkennen waarbij rekening gehouden wordt met: de belief, de afstand tot de zoeklocatie en of een andere agent al dichtbij de lokatie gaat zoeken. Samenvattend zijn de belangrijkste bijdragen van deze thesis de verschillende methoden om personen te zoeken en te volgen in een stedelijke omgeving met één of meer mobiele servicerobots. Alle methoden zijn getest met simulaties en met experimenten met echte robots.