Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/26864
Title: On the valid deterministic localization plan problem
Authors: Sheka, A.
Issue Date: 2013
Citation: Sheka A. On the valid deterministic localization plan problem / A. Sheka // Applied Mathematical Sciences. — 2013. — Vol. 7. — № 97-100. — P. 4829-4838.
Abstract: Grid graphs are popular testbeds for planning with incomplete information. In particular, it is studied a fundamental planning problem, localization, to investigate whether gridworlds make good testbeds for planning with incomplete information. It is found empirically that greedy planning methods that interleave planning and plan execution can localize robots very quickly on random gridworlds or mazes. Thus, they may not provide adequately challenging testbeds. On the other hand, it is showed that finding localization plans that are within a log factor of optimal is NP-hard. Thus there are instances of gridworlds on which all greedy planning methods perform very poorly. These theoretical results help empirical researchers to select appropriate planning methods for planning with incomplete information as well as testbeds to demonstrate them. However, for practical application of difficult instances we need a method for their fast decision. In this paper, we consider an approach to solve localization problem. In particular, we consider an explicit polynomial reduction from the decision version of the valid deterministic localization plan problem to the 3-satisfiability problem. © 2013 Andrey Sheka.
Keywords: 3-SATISFIABILITY PROBLEM
GRID GRAPH
LOCALIZATION PLAN
NPCOMPLETE
URI: http://hdl.handle.net/10995/26864
SCOPUS ID: 84886257674
PURE ID: 855659
ISSN: 1312-885X
DOI: 10.12988/ams.2013.36323
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
scopus-2013-0100.pdf82,39 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.