Category Archives: Planning

automated action planning

Frontier Search and Plan Reconstruction in Oversubscription Planning

Check out work on “Frontier Search and Plan Reconstruction in Oversubscription Planning” – in AAAI 2019

Our paper on “Frontier Search and Plan Reconstruction in Oversubscription Planning” [1] will be presented in The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)

Oversubscription planning (OSP) [2] is a problem of choosing an action sequence which reaches a state with a high utility, given a budget for total action cost. This formulation allows to handle situations with under-constrained resources, which do not allow to achieve all possible goal propositions. In optimal OSP, the task is further constrained to finding a path which achieves a state with maximal utility. Best-First-Branch-and-Bound (BFBB) is a heuristic search algorithm which is widely used for solving OSP problems. <em>BFBB</em> relies on an admissible utility-upper-bounding heuristic function (with budget restrictions) \(h : S \times {\mathbb R}^{0+} \rightarrow R\) to estimate the true utility \(h*(s,b)\).
An incremental BFBB search algorithm with landmark-based approximations (<em>inc-compile-and-BFBB</em>) was proposed for OSP heuristic search [3] to address tasks with non-negative and 0-binary utility functions. <em>inc-compile-and-BFBB</em> maintains the best solution so far and a set of reference states, extended with all the non-redundant value-carrying states discovered during the search. Each iteration requires search re-start in order to exploit the new information obtained along the search. Recent work presented a relative estimation of achievements with value-driven landmarks [4] addressing arbitrary additive utility functions, which incrementally improves the best solution so far eliminating the need to maintain a set of reference states.
This paper [1] proposes a <em>progressive frontier search</em> algorithm, which alleviates the computational cost of search restart once new information is acquired. Our technique allows the new search iteration to continue from any state on the frontier of the previous search iteration, leading to improved efficiency of the search. An extended version of this abstract is available online [5].

[1] D. Muller and E. Karpas, “Frontier search and plan reconstruction in oversubscription planning,” in Aaai, 2018.
[Bibtex]
@inproceedings{muller2018frontier,
title={Frontier Search and Plan Reconstruction in Oversubscription Planning},
author={Muller, Daniel and Karpas, Erez},
booktitle={AAAI},
year={2018}
}
[2] D. E. Smith, “Choosing objectives in over-subscription planning.,” in Icaps, 2004, p. 393.
[Bibtex]
@inproceedings{smith:icaps04,
title={Choosing Objectives in Over-Subscription Planning.},
author={Smith, David E},
booktitle={ICAPS},
volume={4},
pages={393},
year={2004}
}
[3] C. Domshlak and V. Mirkis, “Deterministic oversubscription planning as heuristic search: abstractions and reformulations,” Journal of artificial intelligence research, vol. 52, p. 97–169, 2015.
[Bibtex]
@article{mirkis:domshlak:jair15,
title={Deterministic oversubscription planning as heuristic search: Abstractions and reformulations},
author={Domshlak, Carmel and Mirkis, Vitaly},
journal={Journal of Artificial Intelligence Research},
volume={52},
pages={97--169},
year={2015}
}
[4] D. Muller and E. Karpas, “Value driven landmarks for oversubscription planning.,” in Icaps, 2018.
[Bibtex]
@inproceedings{muller:Karpas:icaps18,
title={Value Driven Landmarks for Oversubscription Planning.},
author={Muller, Daniel and Karpas, Erez},
booktitle={ICAPS},
year={2018}
}
[5] D. Muller and E. Karpas, “Value driven landmarks for oversubscription planning,” Technion, Faculty of Industrial Engineering and Management, IE/IS-2018-04, 2018.
[Bibtex]
@techreport{muller2018TRvalue,
title = {Value Driven Landmarks for Oversubscription Planning},
author = {Muller, Daniel and Karpas, Erez},
year = {2018},
institution = {Technion, Faculty of Industrial Engineering and Management},
number = {IE/IS-2018-04}
}
Logistic Task

Check out my new paper on Automated Tactical Decision Planning Model with Strategic Values Guidance for Local Action-Value-Ambiguity”

In many real-world planning problems, action’s impact differs with a place, time and the context in which the action is applied. The same action with the same effects in a different context or states can cause a different change. In actions with incomplete precondition list, that applicable in several states and circumstances, ambiguity regarding the impact of the action is challenging even in small domains. To estimate the real impact of actions, an evaluation of the effect list will not be enough; a relative estimation is more informative and suitable for estimation of action’s real impact. Recent work on Over-subscription Planning (OSP) defined the net utility of action as the net change in the state’s value caused by the action. The notion of net utility of action allows for a broader perspective on value action impact and use for a more accurate evaluation of achievements of the action, considering inter-state and intra-state dependencies. To achieve value-rational decisions in complex reality often requires strategic, high level, planning with a global perspective and values, while many local tactical decisions require real-time information to estimate the impact of actions. This paper proposes an offline action-value structure analysis to exploit the compactly represented informativeness of net utility of actions to extend the scope of planning to value uncertainty scenarios and to provide a real-time value-rational decision planning tool. The result of the offline pre-processing phase is a compact decision planning model representation for flexible, local reasoning of net utility of actions with (offline) value ambiguity. The obtained flexibility is beneficial for the online planning phase and real-time execution of actions with value ambiguity. Our empirical evaluation shows the effectiveness of this approach in domains with value ambiguity in their action-value-structure.

Automated Tactical Decision Planning Model with Strategic Values Guidance for Local Action-Value-Ambiguity

 Automated Tactical Decision Planning Model with Strategic Values Guidance for Local Action-Value-Ambiguity

 

Optimal utility value ambiguity

 Optimal utility value ambiguity

  • D. Muller and E. Karpas, “Automated tactical decision planning model with strategic values guidance for local action-value-ambiguity,” Arxiv preprint arxiv:1811.12917, 2018.
    [Bibtex]
    @article{muller2018tactic,
    title={Automated Tactical Decision Planning Model with Strategic Values Guidance for Local Action-Value-Ambiguity},
    author={Muller, Daniel and Karpas, Erez},
    journal={arXiv preprint arXiv:1811.12917},
    year={2018}
    }
Economics of Human-AI Ecosystem: Value Bias and Lost Utility in Multi-Dimensional Gaps

Check out my new paper on “Economics of Human-AI Ecosystem: Value Bias and Lost Utility in Multi-Dimensional Gaps”

In recent years, artificial intelligence (AI) decision-making and autonomous systems became an integrated part of the economy, industry, and society. The evolving economy of the human-AI ecosystem raising concerns regarding the risks and values inherited in AI systems. This paper [1] investigates the dynamics of creation and exchange of values and points out gaps in perception of cost-value, knowledge, space and time dimensions. It shows aspects of value bias in human perception of achievements and costs that encoded in AI systems. It also proposes rethinking hard goals definitions and cost-optimal problem-solving principles in the lens of effectiveness and efficiency in the development of trusted machines. The paper suggests a value-driven with cost awareness strategy and principles for problem-solving and planning of effective research progress to address real-world problems that involve diverse forms of achievements, investments, and survival scenarios.

 

DIKW hierarchy

The relation of information and knowledge modeled in
the in DIKW hierarchy (data – information – knowledge –
wisdom)

Different dimensions of costs and values

Different dimensions of costs and values

 

Types of utilities and examples for creating positive and negative utility

Types of utilities and examples for creating positive and negative utility

 

[1] D. Muller, “Economics of human-ai ecosystem: value bias and lost utility in multi-dimensional gap,” Arxiv preprint arxiv:1811.06606, 2018.
[Bibtex]
@article{mullerEconomicsHAI2018,
title={Economics of Human-AI Ecosystem: Value Bias and Lost Utility in Multi-Dimensional Gap},
author={Muller, Daniel},
journal={arXiv preprint arXiv:1811.06606},
year={2018}
}
Oversubscription Planning (OSP) value landmarks

Technical Report for the Paper on Value Driven Landmarks for Oversubscription Planning

A detailed technical report of out ICAPS 2018 paper Value Driven Landmark for Oversubscription Planning is available. In the technical report, we provide detail examples of the theory in the paper. We look closely at the terms of optimality and achievements concerning the complexity of the real-world scenarios. ICAPS 2018 Slides of our presentation along with supplementary material can be found at the publication page.
Starting with the most fundamental question of what additive utility function in OSP problem is, we point out the challenges in multi-valued planning tasks with additive utility setting. We discuss the relationships between state variables and different value assignments to a variable in successive states along a plan. We closely consider negative interactions between state variables with multi-valued (non-zero binary) utility setting, and we show how these negative interactions could occur in tasks with non-negative utility setting.
We treat the OSP task as a process of improvement of the initial state rather than a process of collecting valuable facts is the most basic fundamental of our approach. In contrast to classical planning and partial satisfaction problems where there is one explicit assignment for each variable that is defined as valuable, OSP with additive utility functions allows for each variable to be associated with a set of different utilities. Thus, in the additive utility case, a variable assignment is valuable if its utility is better than the utility at the initial state, where an optimal solution will be the maxima(red circle) l utility over all variables that are {\em mutually consistent}. Therefore, it is easy to see that the concept of {\em improving states} rather than collecting valuable facts is much more suitable for the general case.
In order to capture the properties of the process, we define the net and gross term for the utility of actions which allow us to evaluate achievements with relative terms within the ongoing process of utility maximization. Each process that improves utility must agree with a few several structural properties of optimal. We can define these properties over process due to the definition of the net and gross actions. Finally, we represent these properties with Value-Driven Landmarks, These Value Landmarks are domain-independent (can be applied in each task if sequential decisions or actions), and lead to better performance, sometimes, as you can see in the attached image, without a search at all.
The red circle emphasizes the tasks that solved without search since no plan that meets optimal properties as applicable. In real-world scenarios that involve budget thus is very likely to happen at some point during the search.
Oversubscription action planning with value landmarks - Empirical evaluation of the improving approach

Oversubscription action planning with value landmarks – Empirical evaluation of the improving approach

Stay tuned, we will keep update here the progress of our research and if you find that problem interesting, let us know, there is a lot of work and we will be more than happy to collaborate.

We will soon post a call for collaboration with some of our suggestions.

 

Goal-Oriented Bill Could Do it Better…

Hi,

Here is a new animation explainer I am working on. It comes to clear another point from our research on Oversubscription planning and the merits of value landmarks in a complex (day life) problems with sequential actions.

 

There are some tuning left; I would love to have your comments.
Thanks!