Autonomous navigation in partially known confounding maze-like terrains using D Lite with poisoned reverse

Napoleon H. Reyes, Andre L.C. Barczak, Teo Susniak

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2 Citations (Scopus)

Abstract

This paper presents an extension to the original state-of-the-art D∗Lite algorithm, which is an optimal, informed, complete and incremental search algorithm, suited to goal-directed path-planning in unknown terrains. We strategically modified D∗Lite in order to efficiently address more complex path-planning problems in maze-like environments where the given guiding partial map, plagued with lots of unknown obstacles, leads the robot astray; thereby, requiring the robot to backtrack and perform goal-directed replanning repeatedly many times. In this work, we assume that there is no predecessor nor successor function available during search. Instead, the algorithm is only able to determine the next immediate neighbouring nodes for expansion, and yet it is able to handle the aforementioned cases while still guaranteeing returning an optimal path, if one exists. In order to characterise the proposed algorithm, we have designed test gridworlds in increasing levels of complexity according to a combination of properties: number of necessary replanning stages, number of unknown obstacles encountered, number of backtracking manoeuvres and number of looping dependencies in cell updates. Empirical results on 58 gridworlds show that our proposed D∗Lite with Poisoned Reverse algorithm is superior over the original one, in terms of the number of state expansions, which is largely attributed to the algorithm's running time. Furthermore, analysis of the results show that the reduction in state expansions improve as the complexity of the unknown terrain increases.

Original languageEnglish
Title of host publicationDISA 2018 - IEEE World Symposium on Digital Intelligence for Systems and Machines, Proceedings
EditorsPeter Sincak, Jan Paralic, Laszlo Kovacs, XenFu Wang
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages67-76
Number of pages10
ISBN (Electronic)9781538651025
DOIs
Publication statusPublished - 11 Oct 2018
Externally publishedYes
EventWorld Symposium on Digital Intelligence for Systems and Machines, DISA 2018 - Kosice, Slovakia
Duration: 23 Aug 201825 Aug 2018

Publication series

NameDISA 2018 - IEEE World Symposium on Digital Intelligence for Systems and Machines, Proceedings

Conference

ConferenceWorld Symposium on Digital Intelligence for Systems and Machines, DISA 2018
Abbreviated titleDISA
Country/TerritorySlovakia
CityKosice
Period23/08/1825/08/18

Fingerprint

Dive into the research topics of 'Autonomous navigation in partially known confounding maze-like terrains using D Lite with poisoned reverse'. Together they form a unique fingerprint.

Cite this