Rendezvous on an interval and a search game on a star

Abstract

Rendezvous problems and search games (with two players) are related problems. In a rendezvous problem the players like to meet as soon as possible, while in a search game one of them tries to avoid the meeting as long as possible. So in a rendezvous problem the players have a common interest and in a search game the players have conflicting interests. We consider in this thesis a rendezvous problem on a discrete labeled interval and a search game on a star with players having motion detection abilities. This thesis consists of two parts. The first part (Chapter 2) is about the rendezvous problem on a discrete labeled interval. This problem was first introduced by Alpern in [1]. Most results for this problem are summarized in [2], Chapter 13. This thesis contains new results extending the results in [2]. The work was done in Delft in February 2008 until May 2008 and in July 2008. Moreover a part of the results in Chapter 2 were presented at the 13th International Symposium on Dynamics Games and Applications in Wroclaw, Poland. The second part of this thesis (Chapter 3) is about a search game on a star with players having motion detection abilities. This problem was proposed by Prof. S. Gal (University of Haifa, Israel) and until now no results were available. The work on this problem was done in June 2008 in Haifa resulting in (numerical) solutions for the game and insight in its asymptotic behavior. [1] S. Alpern, The Rendezvous Search Problem, SIAM Journal on Control and Optimization 33 (1995), 673â683. [2] S. Alpern and S. Gal, The Theory of Search Games and Rendezvous, Kluwer Academic Publishers, 2003.