Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

A symbolic programming approach to the rendezvous search problem

Tools
- Tools
+ Tools

Leone, Pierre and Alpern, Steve (2022) A symbolic programming approach to the rendezvous search problem. Operations Research Forum, 3 . 9. doi:10.1007/s43069-022-00122-2

[img]
Preview
PDF
WRAP-symbolic-programming-approach-rendezvous-search-problem-Alpern-2022.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution 4.0.

Download (3229Kb) | Preview
[img] PDF
WRAP-symbolic-programming-approach-rendezvous-search-problem-Alpern-2022.pdf - Accepted Version
Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer.

Download (1755Kb)
Official URL: https://doi.org/10.1007/s43069-022-00122-2

Request Changes to record.

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 M1 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 M2 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 R1 and R2 for the M1 and M2 games respectively. We present an algorithm that computes exactly the rendezvous value of the M1 game as a function of the dropping time z, i.e. z↦R1(z). Then we show that the function R1(z) is locally an affine function and we compute the parameters of the local representations of R1(z). Finally, the rendezvous value of the game R1=minzR1(z) and the optimal dropping times can be determined with the expression of R1(z). The same proceeding can be extended to apply to the problem M2. 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.

Item Type: Journal Article
Subjects: T Technology > T Technology (General)
Divisions: Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences
Faculty of Social Sciences > Warwick Business School
Library of Congress Subject Headings (LCSH): Game theory, Search theory
Journal or Publication Title: Operations Research Forum
Publisher: Springer
ISSN: 2662-2556
Official Date: 31 January 2022
Dates:
DateEvent
31 January 2022Published
5 January 2022Accepted
Volume: 3
Article Number: 9
DOI: 10.1007/s43069-022-00122-2
Status: Peer Reviewed
Publication Status: Published
Reuse Statement (publisher, data, author rights): This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/[insert DOI]
Access rights to Published version: Open Access
Related URLs:
  • Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us