On Computing Plans with Uniform Action Costs
2402.09877
0
0
❗
Abstract
In many real-world planning applications, agents might be interested in finding plans whose actions have costs that are as uniform as possible. Such plans provide agents with a sense of stability and predictability, which are key features when humans are the agents executing plans suggested by planning tools. This paper adapts three uniformity metrics to automated planning, and introduce planning-based compilations that allow to lexicographically optimize sum of action costs and action costs uniformity. Experimental results both in well-known and novel planning benchmarks show that the reformulated tasks can be effectively solved in practice to generate uniform plans.
Create account to get full access
Overview
- Agents in real-world planning applications may want to find plans with uniform action costs to provide stability and predictability
- This paper adapts three uniformity metrics to automated planning and introduces planning-based compilations to optimize for both sum of action costs and action costs uniformity
- Experiments show these reformulated tasks can effectively generate uniform plans in both well-known and novel planning benchmarks
Plain English Explanation
In many real-world situations where planning is used, such as robots navigating a factory floor or AI systems scheduling tasks, the agents (e.g., robots, AI systems) may want to find plans where the actions they take have costs that are as similar or "uniform" as possible. This provides the agents with a sense of stability and predictability, which is important when humans are the ones ultimately executing the plans suggested by the planning tools.
This paper takes three existing ways of measuring how uniform a set of numbers are and adapts them to work with automated planning systems. It also introduces new planning techniques that allow the systems to optimize both for the total cost of the plan and how uniform the individual action costs are. When tested on both well-known planning challenges and some new ones, these reformulated planning tasks were able to effectively generate plans with very uniform action costs.
Technical Explanation
The paper proposes adapting three different uniformity metrics - the coefficient of variation, Gini coefficient, and Variance of Logarithms - to the automated planning domain. It then introduces planning-based compilations that allow these uniformity metrics to be optimized for alongside the total cost of the plan in a lexicographic fashion (optimizing for one objective first, then the other).
Through experimentation on both established planning benchmarks and new custom tasks, the paper demonstrates that these reformulated planning problems can be solved effectively to produce plans with highly uniform action costs. This allows agents to gain the benefits of stability and predictability when executing the plans in the real world.
Critical Analysis
The paper acknowledges that finding plans with perfectly uniform action costs may not always be possible, and provides the ability to balance total plan cost and uniformity as needed. However, it does not discuss potential cases where optimizing for uniformity could lead to less efficient or effective plans overall.
Additionally, the paper focuses on single-agent planning, so further research would be needed to understand how these techniques apply to multi-agent settings where there may be more complex interactions and tradeoffs to consider. Extending this work to handle uncertain or dynamic environments could also be an interesting avenue for future study.
Conclusion
This research provides a way for automated planning systems to generate plans with highly uniform action costs, which can be beneficial for real-world applications where stability and predictability are important. By adapting existing uniformity metrics and introducing new planning-based compilations, the paper demonstrates that these reformulated planning tasks can be solved effectively to produce the desired plans. While there are still some open questions and potential limitations, this work represents a valuable contribution to the field of automated planning.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
Some Orders Are Important: Partially Preserving Orders in Top-Quality Planning
Michael Katz, Junkyu Lee, Jungkoo Kang, Shirin Sohrabi
0
0
The ability to generate multiple plans is central to using planning in real-life applications. Top-quality planners generate sets of such top-cost plans, allowing flexibility in determining equivalent ones. In terms of the order between actions in a plan, the literature only considers two extremes -- either all orders are important, making each plan unique, or all orders are unimportant, treating two plans differing only in the order of actions as equivalent. To allow flexibility in selecting important orders, we propose specifying a subset of actions the orders between which are important, interpolating between the top-quality and unordered top-quality planning problems. We explore the ways of adapting partial order reduction search pruning techniques to address this new computational problem and present experimental evaluations demonstrating the benefits of exploiting such techniques in this setting.
4/3/2024
💬
What's the Plan? Evaluating and Developing Planning-Aware Techniques for Language Models
Eran Hirsch, Guy Uziel, Ateret Anaby-Tavor
0
0
Planning is a fundamental task in artificial intelligence that involves finding a sequence of actions that achieve a specified goal in a given environment. Large language models (LLMs) are increasingly used for applications that require planning capabilities, such as web or embodied agents. In line with recent studies, we demonstrate through experimentation that LLMs lack necessary skills required for planning. Based on these observations, we advocate for the potential of a hybrid approach that combines LLMs with classical planning methodology. Then, we introduce SimPlan, a novel hybrid-method, and evaluate its performance in a new challenging setup. Our extensive experiments across various planning domains demonstrate that SimPlan significantly outperforms existing LLM-based planners.
5/24/2024
Learning Planning Abstractions from Language
Weiyu Liu, Geng Chen, Joy Hsu, Jiayuan Mao, Jiajun Wu
0
0
This paper presents a framework for learning state and action abstractions in sequential decision-making domains. Our framework, planning abstraction from language (PARL), utilizes language-annotated demonstrations to automatically discover a symbolic and abstract action space and induce a latent state abstraction based on it. PARL consists of three stages: 1) recovering object-level and action concepts, 2) learning state abstractions, abstract action feasibility, and transition models, and 3) applying low-level policies for abstract actions. During inference, given the task description, PARL first makes abstract action plans using the latent transition and feasibility functions, then refines the high-level plan using low-level policies. PARL generalizes across scenarios involving novel object instances and environments, unseen concept compositions, and tasks that require longer planning horizons than settings it is trained on.
5/8/2024
Real-World Deployment of a Hierarchical Uncertainty-Aware Collaborative Multiagent Planning System
Martina Stadler Kurtz, Samuel Prentice, Yasmin Veys, Long Quang, Carlos Nieto-Granda, Michael Novitzky, Ethan Stump, Nicholas Roy
0
0
We would like to enable a collaborative multiagent team to navigate at long length scales and under uncertainty in real-world environments. In practice, planning complexity scales with the number of agents in the team, with the length scale of the environment, and with environmental uncertainty. Enabling tractable planning requires developing abstract models that can represent complex, high-quality plans. However, such models often abstract away information needed to generate directly-executable plans for real-world agents in real-world environments, as planning in such detail, especially in the presence of real-world uncertainty, would be computationally intractable. In this paper, we describe the deployment of a planning system that used a hierarchy of planners to execute collaborative multiagent navigation tasks in real-world, unknown environments. By developing a planning system that was robust to failures at every level of the planning hierarchy, we enabled the team to complete collaborative navigation tasks, even in the presence of imperfect planning abstractions and real-world uncertainty. We deployed our approach on a Clearpath Husky-Jackal team navigating in a structured outdoor environment, and demonstrated that the system enabled the agents to successfully execute collaborative plans.
4/29/2024