Path Planning with spatial and temporal Constraints

Abstract

In this thesis we consider different problems arising in the context of planning the movement of objects. The common aspect of these problems is the interaction of spatial and temporal constraints.<br /> The first problem is a pursuit-evasion problem where some <em>lions</em> have the task to 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 <em>et al</em>. showed that n/2 lions are not enough to clear the n x n-grid</nobr>. We consider the same problem in dimension d>2 and prove that order of n^(d-1) / sqrt(d) lions are necessary and sufficient to clear the n^d - 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 to clear the n x n grid is at least n/2 and at most n/2 + order of sqrt(n).<br /> The second main problem is to determine suitable meeting times and locations for a group of participants wishing to schedule a new meeting subject to already scheduled meetings possibly held at a number of different locations. Each participant 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 linear running time. We also analyze several variants of the original problem and provide lower bounds for their solutions.<br /> The third main problem is the path planning for a <em>traveller</em> in an environment which contains moving carriers. While using carrier C, the traveller can walk on C at innate speed v 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'.<br /> Given initial positions of the carriers and of a start position s and a goal position g, is the traveller able to reach g starting from s? If so, what minimum travel time can be achieved?