A Symbolic Programming Approach to the Rendezvous Search Problem

Pierre Leone () and Steve Alpern
Additional contact information
Pierre Leone: University of Geneva
Steve Alpern: University of Warwick

SN Operations Research Forum, 2022, vol. 3, issue 1, 1-29

Abstract: Abstract In this paper we solve the rendezvous problem on the line with markers that can be dropped at chosen times when the initial distance D between the players is known. In the case of one marker, the $$M_1$$ M 1 game, the marker is held by player II at the start of the game and, once dropped and found by player I, indicates in which direction player I must move. In the case of two markers, the $$M_2$$ M 2 game, each player holds one and the dropping times may differ. There is uncertainty regarding the problem initial configuration, and the goal is to minimize the expected rendezvous time that we call the rendezvous value (of the game) denoted $$R_1$$ R 1 and $$R_2$$ R 2 for the $$M_1$$ M 1 and $$M_2$$ M 2 games respectively. We present an algorithm that computes exactly the rendezvous value of the $$M_1$$ M 1 game as a function of the dropping time z, i.e. $$z\mapsto R_1(z)$$ z ↦ R 1 ( z ) . Then we show that the function $$R_1(z)$$ R 1 ( z ) is locally an affine function and we compute the parameters of the local representations of $$R_1(z)$$ R 1 ( z ) . Finally, the rendezvous value of the game $$R_1=min_z R_1(z)$$ R 1 = m i n z R 1 ( z ) and the optimal dropping times can be determined with the expression of $$R_1(z)$$ R 1 ( z ) . The same proceeding can be extended to apply to the problem $$M_2$$ M 2 . Symbolic execution of programs is a classical technique of program testing in computer science, see King [1] for the pioneering work. In this work we adapt the symbolic execution technique to solve an optimization problem. To our knowledge this is the first time that this is attempted, in particular to deal with rendezvous problems.

Keywords: Rendezvous search game on the line; Symbolic programming; Rendezvous with markers; Enumeration of optimal strategies (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-022-00122-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:3:y:2022:i:1:d:10.1007_s43069-022-00122-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-022-00122-2

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().