Fast Heuristic for Ricochet Robots

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61988987%3A17610%2F23%3AA2402HUP" target="_blank" >RIV/61988987:17610/23:A2402HUP - isvavai.cz</a>
Alternative codes found
RIV/68407700:21730/23:00372168
Result on the web
<a href="https://www.scitepress.org/SearchResults.aspx?Context=TiqdMmbpH5G/Nn6Ov+ePvxgxJ1F1l0RLlkAkRMuqeE+H8zlX/4wr2g==&t=1" target="_blank" >https://www.scitepress.org/SearchResults.aspx?Context=TiqdMmbpH5G/Nn6Ov+ePvxgxJ1F1l0RLlkAkRMuqeE+H8zlX/4wr2g==&t=1</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.5220/0011699900003393" target="_blank" >10.5220/0011699900003393</a>

Result language
angličtina
Original language name
Fast Heuristic for Ricochet Robots
Original language description
In this contribution, we describe a fast heuristic for a logical game called Ricochet Robots in which multiple robots cooperate in order to reach a goal. The heuristic recursively explores a restricted search space using subgoals that correspond to interactions of two robots. Subgoals are expanded according to an estimated length of a complete solution, which makes the algorithm reminiscent of the A* algorithm. The estimated length is a lower bound of the length of the real solution, and this allows us to prune subgoals using the best solution found thus far. After eliminating all remaining subgoals, we are guaranteed that the best solution found is the shortest solution from the restricted search space. Moreover, we show that the restricted search space contains a large portion of optimal solutions of the empirical distribution of 1 million random problems. We believe that the presented ideas should generalize to other search problems in which multiple independent agents could block or help each other.
Czech name
—
Czech description
—

Project
<a href="/en/project/LL1902" target="_blank" >LL1902: Powering SMT Solvers by Machine Learning</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach

Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the 15th International Conference on Agents and Artificial Intelligence
ISBN
978-989-758-623-1
ISSN
—
e-ISSN
—
Number of pages
10
Pages from-to
71-79
Publisher name
ICAART
Place of publication
Lisabon
Event location
Lisabon
Event date
Jan 1, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)