Deep Heuristic-learning in the Rubik's Cube Domain: An Experimental Evaluation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10367133" target="_blank" >RIV/00216208:11320/17:10367133 - isvavai.cz</a>

Výsledek na webu

<a href="http://ceur-ws.org/Vol-1885/57.pdf" target="_blank" >http://ceur-ws.org/Vol-1885/57.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Deep Heuristic-learning in the Rubik's Cube Domain: An Experimental Evaluation

Popis výsledku v původním jazyce

Recent successes of neural networks in solving combinatorial problems and games like Go, Poker and others inspire further attempts to use deep learning approaches in discrete domains. In the field of automated planning, the most popular approach is informed forward search driven by a~heuristic function which estimates the quality of encountered states. Designing a~powerful and easily-computable heuristics however is still a~challenging problem on many domains. In this paper, we use machine learning to construct such heuristic automatically. We train a~neural network to predict a~minimal number of moves required to solve a~given instance of Rubik&apos;s cube. We then use the trained network as a~heuristic distance estimator with a~standard forward-search algorithm and compare the results with other heuristics. Our experiments show that the learning approach is competitive with state-of-the-art and might be the best choice in some use-case scenarios.

Název v anglickém jazyce

Deep Heuristic-learning in the Rubik's Cube Domain: An Experimental Evaluation

Popis výsledku anglicky

Recent successes of neural networks in solving combinatorial problems and games like Go, Poker and others inspire further attempts to use deep learning approaches in discrete domains. In the field of automated planning, the most popular approach is informed forward search driven by a~heuristic function which estimates the quality of encountered states. Designing a~powerful and easily-computable heuristics however is still a~challenging problem on many domains. In this paper, we use machine learning to construct such heuristic automatically. We train a~neural network to predict a~minimal number of moves required to solve a~given instance of Rubik&apos;s cube. We then use the trained network as a~heuristic distance estimator with a~standard forward-search algorithm and compare the results with other heuristics. Our experiments show that the learning approach is competitive with state-of-the-art and might be the best choice in some use-case scenarios.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2017

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 17th Conference on Information Technologies - Applications and Theory (ITAT 2017)

ISBN

—

ISSN

1613-0073

e-ISSN

neuvedeno

Počet stran výsledku

8

Strana od-do

57-64

Název nakladatele

CEUR

Místo vydání

Neuveden

Místo konání akce

Martinské hole

Datum konání akce

22. 9. 2017

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

EUR - Evropská akce

Kód UT WoS článku

—