Approximation to the Optimal Strategy in the Mozart Café Problem by Simultaneous Perturbation Stochastic Approximation
Embargo until
Date
2022-05-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Johns Hopkins University
Abstract
The rendezvous search problem is an old and classic problem in operations research. In this problem, two agents with unit speed are placed in some common region and they try to find each other in the least expected time with the assumption that they neither have devices for communication nor necessarily share the same coordinates/directions. In this thesis, we focus on one specific problem in this field, called the “Mozart Café problem,” in which two agents search for each other among n discrete locations (cafés). They can go to any café each day and will stay there the whole day waiting for the other to come, and they wish to minimize the expected time to rendezvous. Previous researchers have found and shown the optimal strategies for n = 2, 3 cases. In this study, we first present some preliminary work on a variant of the general Mozart Café problem on the n = 4 case in which each agent can leave a token in the initial café he visits saying that he would never come back. The optimal strategy on this variant provides a lower bound for the optimal expected rendezvous time in the general n = 4 case. Then we propose a novel modelling technique named k-Markovian modelling where the model parameters can be optimized by stochastic optimization algorithms. This also parameterizes this problem. The aims of this work are to provide a parameterization method and demonstrate the potential to approximate the optimal rendezvous search strategy.
Description
Keywords
Rendezvous Search, Simultaneous Perturbation Stochastic Approximation