Symbolic Search for Optimal Planning with Expressive Extensions
- URL: http://arxiv.org/abs/2204.00288v1
- Date: Fri, 1 Apr 2022 08:41:06 GMT
- Title: Symbolic Search for Optimal Planning with Expressive Extensions
- Authors: David Speck
- Abstract summary: Some properties of a planning problem at hand require an expressive extension of the standard classical planning formalism to capture and model them.
We study planning with axioms, planning with state-dependent action costs, oversubscription planning, and top-k planning.
- Score: 4.36572039512405
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In classical planning, the goal is to derive a course of actions that allows
an intelligent agent to move from any situation it finds itself in to one that
satisfies its goals. Classical planning is considered domain-independent, i.e.,
it is not limited to a particular application and can be used to solve
different types of reasoning problems. In practice, however, some properties of
a planning problem at hand require an expressive extension of the standard
classical planning formalism to capture and model them. Although the importance
of many of these extensions is well known, most planners, especially optimal
planners, do not support these extended planning formalisms. The lack of
support not only limits the use of these planners for certain problems, but
even if it is possible to model the problems without these extensions, it often
leads to increased effort in modeling or makes modeling practically impossible
as the required problem encoding size increases exponentially.
In this thesis, we propose to use symbolic search for cost-optimal planning
for different expressive extensions of classical planning, all capturing
different aspects of the problem. In particular, we study planning with axioms,
planning with state-dependent action costs, oversubscription planning, and
top-k planning. For all formalisms, we present complexity and compilability
results, highlighting that it is desirable and even necessary to natively
support the corresponding features. We analyze symbolic heuristic search and
show that the search performance does not always benefit from the use of a
heuristic and that the search performance can exponentially deteriorate even
under the best possible circumstances, namely the perfect heuristic. This
reinforces that symbolic blind search is the dominant symbolic search strategy
nowadays, on par with other state-of-the-art cost-optimal planning
strategies...
Related papers
- Counting and Reasoning with Plans [19.223883847258158]
We present the first study to quantitative and qualitative reasoning on the plan space.
On the theoretical side, we study its complexity, which gives rise to rich reasoning modes.
Thereby, we transform a planning task into a propositional formula and use knowledge compilation to count different plans.
arXiv Detail & Related papers (2025-01-31T20:03:51Z) - LLM-Generated Heuristics for AI Planning: Do We Even Need Domain-Independence Anymore? [87.71321254733384]
Large language models (LLMs) can generate planning approaches tailored to specific planning problems.
LLMs can achieve state-of-the-art performance on some standard IPC domains.
We discuss whether these results signify a paradigm shift and how they can complement existing planning approaches.
arXiv Detail & Related papers (2025-01-30T22:21:12Z) - On The Planning Abilities of OpenAI's o1 Models: Feasibility, Optimality, and Generalizability [59.72892401927283]
We evaluate the planning capabilities of OpenAI's o1 models across a variety of benchmark tasks.
Our results reveal that o1-preview outperforms GPT-4 in adhering to task constraints.
arXiv Detail & Related papers (2024-09-30T03:58:43Z) - Unlocking Reasoning Potential in Large Langauge Models by Scaling Code-form Planning [94.76546523689113]
We introduce CodePlan, a framework that generates and follows textcode-form plans -- pseudocode that outlines high-level, structured reasoning processes.
CodePlan effectively captures the rich semantics and control flows inherent to sophisticated reasoning tasks.
It achieves a 25.1% relative improvement compared with directly generating responses.
arXiv Detail & Related papers (2024-09-19T04:13:58Z) - Learning adaptive planning representations with natural language
guidance [90.24449752926866]
This paper describes Ada, a framework for automatically constructing task-specific planning representations.
Ada interactively learns a library of planner-compatible high-level action abstractions and low-level controllers adapted to a particular domain of planning tasks.
arXiv Detail & Related papers (2023-12-13T23:35:31Z) - A Planning Ontology to Represent and Exploit Planning Knowledge for Performance Efficiency [6.87593454486392]
We consider the problem of automated planning, where the objective is to find a sequence of actions that will move an agent from an initial state of the world to a desired goal state.
We hypothesize that given a large number of available planners and diverse planning domains; they carry essential information that can be leveraged to identify suitable planners and improve their performance for a domain.
arXiv Detail & Related papers (2023-07-25T14:51:07Z) - A Framework for Neurosymbolic Robot Action Planning using Large Language Models [3.0501524254444767]
We present a framework aimed at bridging the gap between symbolic task planning and machine learning approaches.
The rationale is training Large Language Models (LLMs) into a neurosymbolic task planner compatible with the Planning Domain Definition Language (PDDL)
Preliminary results in selected domains show that our method can: (i) solve 95.5% of problems in a test data set of 1,000 samples; (ii) produce plans up to 13.5% shorter than a traditional symbolic planner; (iii) reduce average overall waiting times for a plan availability by up to 61.4%.
arXiv Detail & Related papers (2023-03-01T11:54:22Z) - Temporal Planning with Incomplete Knowledge and Perceptual Information [0.0]
This paper presents a new planning approach that combines contingent plan construction within a temporal planning framework.
We propose a small extension to the Planning Domain Definition Language (PDDL) to model incomplete, (ii) knowledge sensing actions.
We also introduce a new set of planning domains to evaluate our solver, which has shown good performance on a variety of problems.
arXiv Detail & Related papers (2022-07-20T07:26:08Z) - Task Scoping: Generating Task-Specific Abstractions for Planning [19.411900372400183]
Planning to solve any specific task using an open-scope world model is computationally intractable.
We propose task scoping: a method that exploits knowledge of the initial condition, goal condition, and transition-dynamics structure of a task.
We prove that task scoping never deletes relevant factors or actions, characterize its computational complexity, and characterize the planning problems for which it is especially useful.
arXiv Detail & Related papers (2020-10-17T21:19:25Z) - Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
We consider alternatives to an implicit sequential planning assumption.
We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan.
We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
arXiv Detail & Related papers (2020-04-23T18:08:58Z) - STRIPS Action Discovery [67.73368413278631]
Recent approaches have shown the success of classical planning at synthesizing action models even when all intermediate states are missing.
We propose a new algorithm to unsupervisedly synthesize STRIPS action models with a classical planner when action signatures are unknown.
arXiv Detail & Related papers (2020-01-30T17:08:39Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.