Cost-Optimal Planning, Delete Relaxation, Approximability, and Heuristics

Bäckström, ChristerLinköpings universitet,Programvara och system,Tekniska fakulteten (författare)

Funding Agencies|Swedish Research Council (VR)Swedish Research Council [621-2014-4086]; VRSwedish Research Council [2017-04112]
Cost-optimal planning is a very well-studied topic within planning, and it has proven to be computationally hard both in theory and in practice. Since cost-optimal planning is an optimisation problem, it is natural to analyse it through the lens of approximation. An important reason for studying cost-optimal planning is heuristic search; heuristic functions that guide the search in planning can often be viewed as algorithms solving or approximating certain optimisation problems. Many heuristic functions (such as the ubiquitious h(+) heuristic) are based on delete relaxation, which ignores negative effects of actions. Planning for instances where the actions have no negative effects is often referred to as monotone planning. The aim of this article is to analyse the approximability of cost-optimal monotone planning, and thus the performance of relevant heuristic functions. Our findings imply that it may be beneficial to study these kind of problems within the framework of parameterised complexity and we initiate work in this direction.

Jonsson, PeterLinköpings universitet,Programvara och system,Tekniska fakulteten(Swepub:liu)petjo00 (författare)
Ordyniak, SebastianUniv Leeds, England (författare)
Linköpings universitetProgramvara och system (creator_code:org_t)

Ingår i:The journal of artificial intelligence research: AI ACCESS FOUNDATION70, s. 169-2041076-97571943-5037

Av författaren/redakt...: Bäckström, Chris ...; Jonsson, Peter; Ordyniak, Sebast ...

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.