Knowledge-Based Programs as Plans: Succinctness and the Complexity of Plan Existence
Knowledge-based programs (KBPs) are high-level protocols describing the course of action an agent should perform as a function of its knowledge. The use of KBPs for expressing action policies in AI planning has been surprisingly overlooked. Given that to each KBP corresponds an equivalent plan and vice versa, KBPs are typically more succinct than standard plans, but imply more on-line computation time. Here we make this argument formal, and prove that there exists an exponential succinctness gap between knowledge-based programs and standard plans. Then we address the complexity of plan existence. Some results trivially follow from results already known from the literature on planning under incomplete knowledge, but many were unknown so far.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity
We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL: the succinctness problem for first-order rewritings of ontology-mediated queries…
Representation and Synthesis of C++ Programs for Generalized Planning
The paper introduces a novel representation for Generalized Planning (GP) problems, and their solutions, as C++ programs. Our C++ representation allows to formally proving the termination of generalized plans, and to spe…
Heuristic SearchCode Driven Planning with Domain-Adaptive Critic
Large Language Models (LLMs) have been widely adopted as task planners for AI agents in sequential decision-making problems, leveraging their extensive world knowledge. However, the gap between their general knowledge an…
General KnowledgeStarcraft IIJoint Verification and Refinement of Language Models for Safety-Constrained Planning
Although pre-trained language models can generate executable plans (e.g., programmatic policies) for solving robot tasks, the generated plans may violate task-relevant logical specifications due to the models' black-box …
Language ModelingLanguage ModellingCapturing (Optimal) Relaxed Plans with Stable and Supported Models of Logic Programs
We establish a novel relation between delete-free planning, an important task for the AI Planning community also known as relaxed planning, and logic programming. We show that given a planning problem, all subsets of act…
Diagnostic