Preference-based planning: Difference between revisions

Revision as of 06:46, 24 June 2010

Latest revision as of 05:42, 23 July 2024

(25 intermediate revisions by 10 users not shown)

Line 1:

{{Short description|Form of automated planning and scheduling}}

In [[artificial intelligence]], '''preference-based planning''' is a form of [[automated planning and scheduling]] which focuses on producing plans that additionally satisfy as many user-specified [[preference]]s as possible. In many [[problem ___domain]]sdomains, a task can be accomplished by various sequences of actions (also known as plans). These plans can vary in quality: there can be many ways to solve a problem, but onepreferred generally prefersare a wayways that ismore, e.g., cost-effective, quick, and safe.

Preference-based planners take these preferences into account when producing a plan for a given problem. Examples of preference-based planning software include ''PPLAN''<ref name="pplan">[http://www.cs.toronto.edu/~sheila/PPLAN/ PPLAN], Bienvenu et al.</ref> and ''HTNPlan-P''<ref name="htnplanp">[http://www.cs.toronto.edu/kr/publications/1242050782_Sohrabi-IJCAI09.pdf HTN Planning with Preferences], Sohrabi et al.</ref> (preference-based [[Hierarchicalhierarchical task network|]] (HTN) planning]]).

== Overview ==

Preferences can be regarded as soft constraints on a plan. The quality of a plan increases when more preferences are satisfied but it may not be possible to satisfy all preferences in a singleone plan. This differs from hard constraints which must be satisfied in all plans produced by the planning software. These hard constraints are part of the [[___domain knowledge]] while the soft constraints (or preferences) are separately specified by the user. This allows the same ___domain knowledge to be reused for various users who may have different preferences.

The use of preferences may also increase the length of a plan in order to satisfy more preferences. For example, when planning a journey from home to school, the user may prefer to buy a cup of coffee along the way. The planning software could now plan to visit [[Starbucks]]the coffee shop first and then continue to school.<ref name="starbucks">[http://www.cs.nmsu.edu/~tson/papers/tplp-plan-prefs.pdf Planning with Preferences using Logic Programming], Son and Pontelli</ref> This increases the length of the plan but the user's preference is satisfied.

Preferences can be regarded as soft constraints on a plan. The quality of a plan increases when more preferences are satisfied but it may not be possible to satisfy all preferences in a single plan. This differs from hard constraints which must be satisfied in all plans produced by the planning software. These hard constraints are part of the ___domain knowledge while the soft constraints (or preferences) are separately specified by the user. This allows the same ___domain knowledge to be reused for various users who may have different preferences.

The use of preferences may also increase the length of a plan in order to satisfy more preferences. For example, when planning a journey from home to school, the user may prefer to buy a cup of coffee along the way. The planning software could now plan to visit [[Starbucks]] first and then continue to school.<ref name="starbucks">[http://www.cs.nmsu.edu/~tson/papers/tplp-plan-prefs.pdf Planning with Preferences using Logic Programming], Son and Pontelli</ref> This increases the length of the plan but the user's preference is satisfied.

== Planning Domain Definition Language ==

The [[Planning Domain Definition Language]], as of version 3.0,<ref name="pddl3">[https://dx.doi.org/10.1016/j.artint.2008.10.012 Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners], Gerevini et al.</ref> supports the specification of preferences through <code>preference</code> statements. For example, the statement

:<code>(preference (always (clean room1)))</code>

The [[Planning Domain Definition Language]] (as of version 3.0<ref name="pddl3">[http://www.cs.yale.edu/homes/dvm/papers/pddl-ipc5.pdf Plan Constraints and Preferences in PDDL3], Gerevini and Long</ref>) supports the specification of preferences through <code>preference</code> statements. For example, the statement <code>(preference (always (clean room1)))</code> indicates that the user prefers that <code>room1</code> should be clean at each state of the plan. In other words, the planner should not schedule an action that causes <code>room1</code> to become dirty. As this example shows and in general, a preference is evaluated with regard to all states of a plan (if [[Semantics|semantically]] required).

In addition to <code>always</code>, other constructs based on [[linear temporal logic]] are also supported, such as <code>sometime</code> (at least once during the plan), <code>sometime-after</code> (to be planned after a particular state) and <code>at-most-once</code> (the preference holds during at most one sequence of states in the plan).

=== Plan quality ===

== Constraints satisfaction problem ==

In addition to determining whether a preference is satisfied, we also need to compute the quality of a plan based on how many preferences are satisfied. For this purpose, PDDL 3.0 includes an expression called <code>is-violated <name></code> which is equal to "the number of distinct preferences with the given name that are not satisfied in the plan".<ref name="pddl3"/> For a plan, a value can now be computed using a metric function, which is specified with <code>:metric</code>:

:<code>(:metric minimize (+ (* 5 (is-violated pref1)) (* 7 (is-violated pref2))))</code>

This example metric function specifies that the calculated value of the plan should be minimized (i.e., a plan with value ''v1'' and a plan with value ''v2'' such that ''v1'' < ''v2'', the former plan is strictly preferred). The value of a plan is computed by the given function, which is expressed in [[Polish notation]]. In this case, violation of the second preference, <code>pref2</code>, has been given a greater penalty than the first preference, <code>pref1</code>.

== Constraints satisfaction problem ==

In the area of [[constraint satisfaction problem]]s, flexible variants exist that deal with soft constraints in a similar way to preferences in preference-based planning.

==References==

{{Reflist}}

<references/>

{{Automated reasoning}}

[[Category:Automated planning and scheduling]]

[[Category:Strategic management]]