Search-and-rescue rendezvous
We consider a new type of asymmetric rendezvous search problem in which player II needs to give player I a ‘gift’ which can be in the form of information or material. The gift can either be transfered upon meeting, as in traditional rendezvous, or it can be dropped off by player II at a location he...
Published in: | European Journal of Operational Research |
---|---|
Main Authors: | , , |
Format: | Article in Journal/Newspaper |
Language: | unknown |
Published: |
Elsevier
2022
|
Subjects: | |
Online Access: | https://wrap.warwick.ac.uk/152722/ https://wrap.warwick.ac.uk/152722/7/WRAP-search-rescue-rendezvous-Alpern-2021.pdf https://wrap.warwick.ac.uk/152722/1/WRAP-search-rescue-rendezvous-Alpern-2021.pdf https://doi.org/10.1016/j.ejor.2021.05.009 |
id |
ftuwarwick:oai:wrap.warwick.ac.uk:152722 |
---|---|
record_format |
openpolar |
spelling |
ftuwarwick:oai:wrap.warwick.ac.uk:152722 2024-04-21T07:52:38+00:00 Search-and-rescue rendezvous Leonea, Pierre Buwaya, Julia Alpern, Steve 2022-03-01 application/pdf https://wrap.warwick.ac.uk/152722/ https://wrap.warwick.ac.uk/152722/7/WRAP-search-rescue-rendezvous-Alpern-2021.pdf https://wrap.warwick.ac.uk/152722/1/WRAP-search-rescue-rendezvous-Alpern-2021.pdf https://doi.org/10.1016/j.ejor.2021.05.009 unknown Elsevier https://wrap.warwick.ac.uk/152722/7/WRAP-search-rescue-rendezvous-Alpern-2021.pdf https://wrap.warwick.ac.uk/152722/1/WRAP-search-rescue-rendezvous-Alpern-2021.pdf Leonea, Pierre, Buwaya, Julia and Alpern, Steve (2022) Search-and-rescue rendezvous. European Journal of Operational Research, 297 (2). pp. 579-591. doi:10.1016/j.ejor.2021.05.009 <http://dx.doi.org/10.1016/j.ejor.2021.05.009> ISSN 0377-2217. T Technology (General) Journal Article NonPeerReviewed 2022 ftuwarwick https://doi.org/10.1016/j.ejor.2021.05.009 2024-03-27T15:32:14Z We consider a new type of asymmetric rendezvous search problem in which player II needs to give player I a ‘gift’ which can be in the form of information or material. The gift can either be transfered upon meeting, as in traditional rendezvous, or it can be dropped off by player II at a location he passes, in the hope it will be found by player I. The gift might be a water bottle for a traveller lost in the desert; a supply cache for Captain Scott in the Antarctic; or important information (left as a gift). The common aim of the two players is to minimize the time taken for I to either meet II or find the gift. We find optimal agent paths and drop off times when the search region is a line, the initial distance between the players is known and one or both of the players can leave gifts. A novel and important technique introduced in this paper is the use of families of linear programs to solve this and previous rendezvous problems. Previously, the approach was to guess the answer and then prove it was optimal. Our work has applications to other forms of rendezvous on the line: we can solve the symmetric version (players must use the same strategy) with two gifts and we show that there are no asymmetric solutions to this two gifts problem. We also solve the GiftStart problem, where the gift or gifts must be dropped at the start of the game. Furthermore, we can solve the Minmax version of the game where the objective function is to minimize the maximum rendezvous time. This problem admits variations where players have 0, 1 or 2 gifts at disposal. In particular, we show that the classical Wait For Mommy strategy is optimal for this setting. Article in Journal/Newspaper Antarc* Antarctic The University of Warwick: WRAP - Warwick Research Archive Portal European Journal of Operational Research |
institution |
Open Polar |
collection |
The University of Warwick: WRAP - Warwick Research Archive Portal |
op_collection_id |
ftuwarwick |
language |
unknown |
topic |
T Technology (General) |
spellingShingle |
T Technology (General) Leonea, Pierre Buwaya, Julia Alpern, Steve Search-and-rescue rendezvous |
topic_facet |
T Technology (General) |
description |
We consider a new type of asymmetric rendezvous search problem in which player II needs to give player I a ‘gift’ which can be in the form of information or material. The gift can either be transfered upon meeting, as in traditional rendezvous, or it can be dropped off by player II at a location he passes, in the hope it will be found by player I. The gift might be a water bottle for a traveller lost in the desert; a supply cache for Captain Scott in the Antarctic; or important information (left as a gift). The common aim of the two players is to minimize the time taken for I to either meet II or find the gift. We find optimal agent paths and drop off times when the search region is a line, the initial distance between the players is known and one or both of the players can leave gifts. A novel and important technique introduced in this paper is the use of families of linear programs to solve this and previous rendezvous problems. Previously, the approach was to guess the answer and then prove it was optimal. Our work has applications to other forms of rendezvous on the line: we can solve the symmetric version (players must use the same strategy) with two gifts and we show that there are no asymmetric solutions to this two gifts problem. We also solve the GiftStart problem, where the gift or gifts must be dropped at the start of the game. Furthermore, we can solve the Minmax version of the game where the objective function is to minimize the maximum rendezvous time. This problem admits variations where players have 0, 1 or 2 gifts at disposal. In particular, we show that the classical Wait For Mommy strategy is optimal for this setting. |
format |
Article in Journal/Newspaper |
author |
Leonea, Pierre Buwaya, Julia Alpern, Steve |
author_facet |
Leonea, Pierre Buwaya, Julia Alpern, Steve |
author_sort |
Leonea, Pierre |
title |
Search-and-rescue rendezvous |
title_short |
Search-and-rescue rendezvous |
title_full |
Search-and-rescue rendezvous |
title_fullStr |
Search-and-rescue rendezvous |
title_full_unstemmed |
Search-and-rescue rendezvous |
title_sort |
search-and-rescue rendezvous |
publisher |
Elsevier |
publishDate |
2022 |
url |
https://wrap.warwick.ac.uk/152722/ https://wrap.warwick.ac.uk/152722/7/WRAP-search-rescue-rendezvous-Alpern-2021.pdf https://wrap.warwick.ac.uk/152722/1/WRAP-search-rescue-rendezvous-Alpern-2021.pdf https://doi.org/10.1016/j.ejor.2021.05.009 |
genre |
Antarc* Antarctic |
genre_facet |
Antarc* Antarctic |
op_relation |
https://wrap.warwick.ac.uk/152722/7/WRAP-search-rescue-rendezvous-Alpern-2021.pdf https://wrap.warwick.ac.uk/152722/1/WRAP-search-rescue-rendezvous-Alpern-2021.pdf Leonea, Pierre, Buwaya, Julia and Alpern, Steve (2022) Search-and-rescue rendezvous. European Journal of Operational Research, 297 (2). pp. 579-591. doi:10.1016/j.ejor.2021.05.009 <http://dx.doi.org/10.1016/j.ejor.2021.05.009> ISSN 0377-2217. |
op_doi |
https://doi.org/10.1016/j.ejor.2021.05.009 |
container_title |
European Journal of Operational Research |
_version_ |
1796935844149329920 |