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

Florian Berger

Sujets

• Informatik

Informations

• Publié par: rheinische_friedrich-wilhelms-universitat_bonn
• Publié le: 01 janvier 2010
• Nombre de lectures: 37
• Langue: English

Extrait

Path Planning with spatial
and temporal Constraints
Dissertation
Zur Erlangung des Doktorgrades (Dr. rer. nat.)
der Mathematisch-Naturwissenschaftlichen Fakult¨at
der Rheinischen Friedrich-Wilhelms-Universit¨at Bonn
vorgelegt von
Florian Berger
aus Hamburg
Bonn, September 20102
AngefertigtmitderGenehmigungderMathematisch-NaturwissenschaftlichenFakult¨at
der Rheinischen Friedrich-Wilhelms-Universita¨t Bonn
Gutachter: Prof. Dr. Rolf Klein, Universit¨at Bonn
Prof. Dr. Norbert Blum, Universita¨t Bonn
Tag der mu¨ndlichen Pru¨fung: 19. Januar 2011
Diese Dissertation ist auf dem Hochschulschriftenserver der ULB Bonn unter
http://hss.ulb.uni-bonn.de/diss online elektronisch publiziert.
Erscheinungsjahr: 2011Abstract
In this thesis we consider different problems arising in the co ntext of planning the
movement of objects. The common aspect of these problems is the interaction of
spatial and temporal constraints.
The three main problems analyzed are:
∙ Thefirstproblemisapursuit-evasionproblemwheresomelions havethetaskto
clear a grid graph whose nodes are initially contaminated. The contamination
spreads one step per time unit in each direction not blocked by a lion. A vertex
is cleared from its contamination whenever a lion moves to it. Brass et al. [21]
nshowedthat lionsarenotenoughtoclearthen×n-grid. Weconsiderthesame
2 √
d−1problem in dimension d > 2 and prove that Θ(n / d) lions are necessary
dand sufficient to clear the n -grid. Furthermore, we consider a 2-dimensional
problem variant where the movement of the lions is not restricted to the edges
of the grid. Lions are allowed to jump from grid vertices to non-adjacent grid
vertices. For this problem variant we can show that the number of lions needed√
n nto clear the n×n-grid is at least and at most +O( n).
2 2
∙ The second main problem is to determine suitable meeting times and locations
for agroupof participants wishingto scheduleanewmeeting subjectto already
scheduled meetings possibly held at a number of different loca tions. Each par-
ticipant must be able to reach the new meeting location, attend for the entire
duration, and reach the next meeting location on time. We apply the concept
of LP-type problems which leads to a randomized algorithm with expected lin-
ear running time. We also analyze several variants of the original problem and
provide lower bounds for their solutions.
∙ The third main problem is the path planning for a traveller in an environment
which contains moving carriers. While using carrier C, the traveller can walk
onC at innate speedv≥0 in any direction, like a passenger on board a vessel.
Whenever his current position on C is simultaneously contained in some other
′ ′ ′carrier C , the traveller can change from C to C , and continue his tour by C .
Given initial positions of the carriers and of a start position s and a goal po-
sition g, is the traveller able to reach g starting from s? If so, what minimum
travel time can be achieved?
In dimension 8 and higher, the problem is undecidable. An interesting case
is in dimension 2. We prove that the problem is NP-hard, even if all carriers
are vertical line segments. It turns out that an s-to-g path of finite duration
may require an infinite number of carrier changes. Despite this difficulty, we
can show that the two-dimensional problem is decidable if the carriers are lines
or line segments. In addition, we provide a pseudo-polynomial approximation
algorithm for the case that the carriers are bounded.Acknowledgments
First of all, I would like to thankmy advisor, Prof. Rolf Klein, for introducingme to
the field of computational geometry, giving me the opportunity to write this thesis,
and for many fruitful discussions. I am thankful to him and my other co-authors
and colleagues.
I want to mention
Alexander Gilbers, Dr. Ansgar Gru¨ne, Daniel Jung, Dr. Tom Kamphans, Martin
Ko¨hler,Dr.ElmarLangetepe, Prof.DoronNussbaum,RainerPenninger,Prof.J¨org-
Ru¨diger Sack and Dr. Jiehua Yi.
Also I would like to thank Antje Bertram and Mariele Knepper for assistance with
administrative tasks.
Additionally, Iwouldlike toacknowledge withthanksProf.DanielBienstock, Henry
Bottomley, Dr. Thomas B¨ohme, Prof. Frank Dehne, Prof. Adrian Dumitrescu,
Prof. David Eppstein, Prof. Fedor V. Fomin, Dr. J´eroˆme Galtier, Prof. David
Kirkpatrick, Prof. Imre Leader, Friedrich Regen, Prof. Gu¨nter Rote, Jakob So¨hl,
Prof. Dimitrios M. Thilikos and Prof. Emo Welzl for valuable discussions or helpful
advice on known results.
I am especially thankful to Prof. J¨org-Ru¨diger Sack. He offe red me the opportunity
for a research stay abroad.
Above all, warmest thanks to my parents, Irene and Uwe Berger, for their constant
encouragement and continuous support.
Thanks to all of you!Contents
1 Introduction 1
1.1 Problems in path planning . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview of this thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 How many Lions are needed to clear a Grid? 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Results in dimension 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Results on d-dimensional grids . . . . . . . . . . . . . . . . . . . . . . 16
2.4.1 Upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.2 Lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.3 Asymptotic estimate . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5 Flying lions in the 2-dimensional grid. . . . . . . . . . . . . . . . . . . 22
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Meeting Scheduling respecting Time and Space 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Geometric interpretation of the problem . . . . . . . . . . . . . . . . . 29
3.4 LP-approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4.1 General framework of LP-type problems . . . . . . . . . . . . . 31
3.4.2 Preparations for applying the general framework . . . . . . . . 31
3.4.3 Application of the general framework. . . . . . . . . . . . . . . 34
3.4.4 Allowing participants to travel at different speeds . . . . . . . . 36
VVI CONTENTS
3.5 Allowing k participants to be absent . . . . . . . . . . . . . . . . . . . 38
3.6 Maximizing the number of participants . . . . . . . . . . . . . . . . . . 40
3.7 Multiple meeting locations . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.8 More than 2 previously scheduled meetings . . . . . . . . . . . . . . . 41
3.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4 Traveller’s Problem 45
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.1.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1.2 Surprising properties of traveller paths . . . . . . . . . . . . . . 49
4.1.3 Overview of the results of this chapter . . . . . . . . . . . . . . 53
4.2 Subintervals with finitely many carrier changes . . . . . . . . . . . . . 53
4.3 Higher dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.4 Dimension two . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4.1 NP-hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4.2 Decidability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.4.2.1 Analyzing paths by means of the graph G . . . . . . . 67
4.4.2.2 Propagation of reachable points . . . . . . . . . . . . 71
4.4.2.3 Treatment of Zeno cycles . . . . . . . . . . . . . . . . 75
4.4.3 Pseudo-polynomial approximation . . . . . . . . . . . . . . . . 81
4.5 Uncountable many paths and the Cantor set . . . . . . . . . . . . . . 84
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
List of Figures 87
Bibliography 89Chapter 1
Introduction
1.1 Problems in path planning
Designing suitable paths for movable objects is a crucial task in many scenarios.
Motionplanninginvolvessuchdiverseaspectsascomputingcollision-freepathsamong
possibly moving obstacles, coordinating the motions of several robots, and planning
sliding and pushing motions to achieve precise relations among objects. An overview
of motion planning is given in the books by Latombe [46] and LaValle [47].
A simple example for one basic problem in motion planning is to find the shortest
path from a source to a destination in a scene given by a simple polygon [49].
Many different variations of such problems are possible which leads to a rich number
of interesting problems. Let us mention only a few possible variants:
∙ Are all information given in advance or does the robot achieve further informa-
tion while moving? Corresponding problems are called offline in the first case
and online inthe second case. Inthisthesisourfocusison theoffline problems.
∙ How is the movement of the robot modeled?
∙ Is the shape of the robot given by a