Fast Heuristic for Ricochet Robots

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/68407700:21730/23:00372168

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Fast Heuristic for Ricochet Robots

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Fast Heuristic for Ricochet Robots

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

<a href="/cs/project/LL1902" target="_blank" >LL1902: Obohacování SMT řešičů pomocí strojového učení</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2023

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proceedings of the 15th International Conference on Agents and Artificial Intelligence

ISBN

978-989-758-623-1

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

71-79

Název nakladatele

ICAART

Místo vydání

Lisabon

Místo konání akce

Lisabon

Datum konání akce

1. 1. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—