Path planning with spatial and temporal constraints [Elektronische Ressource] / vorgelegt von Florian Berger

Path Planning with spatialand temporal ConstraintsDissertationZur Erlangung des Doktorgrades (Dr. rer. nat.)der Mathematisch-Naturwissenschaftlichen Fakult¨atder Rheinischen Friedrich-Wilhelms-Universit¨at Bonnvorgelegt vonFlorian Bergeraus HamburgBonn, September 20102AngefertigtmitderGenehmigungderMathematisch-NaturwissenschaftlichenFakult¨atder Rheinischen Friedrich-Wilhelms-Universita¨t BonnGutachter: Prof. Dr. Rolf Klein, Universit¨at BonnProf. Dr. Norbert Blum, Universita¨t BonnTag der mu¨ndlichen Pru¨fung: 19. Januar 2011Diese Dissertation ist auf dem Hochschulschriftenserver der ULB Bonn unterhttp://hss.ulb.uni-bonn.de/diss online elektronisch publiziert.Erscheinungsjahr: 2011AbstractIn this thesis we consider different problems arising in the co ntext of planning themovement of objects. The common aspect of these problems is the interaction ofspatial and temporal constraints.The three main problems analyzed are:∙ Thefirstproblemisapursuit-evasionproblemwheresomelions havethetasktoclear a grid graph whose nodes are initially contaminated. The contaminationspreads one step per time unit in each direction not blocked by a lion. A vertexis cleared from its contamination whenever a lion moves to it. Brass et al. [21]nshowedthat lionsarenotenoughtoclearthen×n-grid. Weconsiderthesame2 √d−1problem in dimension d > 2 and prove that Θ(n / d) lions are necessarydand sufficient to clear the n -grid.