is Íslenska en English

Lokaverkefni (Meistara)

Háskólinn í Reykjavík > Tæknisvið / School of Technology > MSc Tölvunarfræðideild / Department of Computer Science >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/7491

Titill: 
  • Titill er á ensku Backtracking and value back-propagation in real-time search
Námsstig: 
  • Meistara
Leiðbeinandi: 
Útdráttur: 
  • Útdráttur er á ensku

    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.

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

Samþykkt: 
  • 1.2.2011
URI: 
  • http://hdl.handle.net/1946/7491


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
MSc_Sverrir-Sigmundarson.pdf1.7 MBOpinnHeildartextiPDFSkoða/Opna