EnglishisÍslenska

Member institutions

Search in


ThesisReykjavík University>Tölvunarfræðideild>Meistaraprófsritgerðir>

Please use this identifier to cite or link to this item: http://hdl.handle.net/1946/7491

Title

Backtracking and value back-propagation in real-time search

Published
June 2006
Abstracts
  • Learning real-time search allows intelligent agents to improve their performance by learning from experience. By interleaving their planning and execution steps they can, in constant time, decide on which action to take from their current state based on limited or incomplete information. This thesis focuses primarily on real-time algorithms that converge to optimal solutions through repeated trials. This work concentrates on two things, firstly it provides an extensive evaluation of established real-time algorithms that seek optimal solutions. While validating earlier research, this evaluation sheds new light on certain behavioral aspects of the algorithms and summarizes their most important properties. Secondly, the thesis examines in detail two types of real-time search enhancements, backtracking and value back-propagation. Based on this analysis, these two enhancements are re-formulated and avenues for their integration into the original LRTA* algorithm are presented. The new search enhancements are shown to improve significantly upon other real-time algorithms and provide a better combination of value back-propagating and backtracking than previous backtracking algorithms.

  • is

    Rauntíma lærdómsaðferðir gera greindum forritum kleift að bæta afköst sín með því að læra af reynslu. Með samtvinnaðri áætlunargerð og framkvæmd þá geta forritin, innan skildgreinds tíma, ákvarðað áætlaða bestu ákvörðun frá núverandi stöðu. Þessa ákvörðun geta þau tekið þó einungis liggi fyrir takmarkaðar eða ófullkomnar upplýsingar um umhverfi og stöðu þeirra. Í þessari ritgerð er sjónum eingöngu beint að rauntíma aðferðum sem tryggja að bestu lausnir á vandamálum finnist með ítruðum prófunaraðferðum. Efni ritgerðarinnar skiptist í tvennt, annars vegar er kynnt víðtæk samanburðarrannsókn á rauntímaaðferðum sem tryggja bestu lausnir. Um leið og niðurstöður þessarar samanburðarrannsóknar staðfestir niðurstöður fyrri rannsakenda, þá varpar rannsóknin nýju ljósi á ákveðin hegðunarmynstur aðferðanna og gefur yfirlit yfir afköst og helstu eiginleika þeirra. Hins vegar skoðum við í ritgerðinni ítarlega tvær tegundir betrumbóta á rauntíma aðferðum, þ.e. rakningu og upplýsingaútbreiðslu. Við umbreytum framsetningu þeirra lítillega og kynnum hvernig mögulegt er að nýta breyttu aðferðirnar sem hluta af LRTA* reikniritinu. Við birtum niðurstöður sem sýna að betrumbætur okkar auka umtalsvert afköst eldri rauntímaleitaraðferða ásamt því að sameina betur en áður hefur verið mögulegt, notkun rakningar og upplýsingaútbreiðslu í rauntímaleitum.

Comments
is

Tölvunarfræði, Thesis

Issued Date
01/02/2011


Artifacts
Name[Sortable]Size[Sortable]Visibility[Sortable]Description[Sortable]Format
MSc_Sverrir-Sigmun... .pdf1.74MBOpen Complete Text PDF View/Open