In artificial intelligence

Artificial intelligence

Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...

, preference-based planning is a form of automated planning and scheduling

Automated planning and scheduling

Automated planning and scheduling is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles. Unlike classical control and classification problems, the solutions are...

 which focuses on producing plans that additionally satisfy as many user-specified preference

Preference

-Definitions in different disciplines:The term “preferences” is used in a variety of related, but not identical, ways in the scientific literature. This makes it necessary to make explicit the sense in which the term is used in different social sciences....

s as possible. In many problem domain

Problem domain

A problem domain is the area of expertise or application that needs to be examined to solve a problem. A problem domain is simply looking at only the topics you are interested in, and excluding everything else. For example, if you were developing a system trying to measure good practice in...

s, 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 one generally prefers a way that is, 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 and HTNPlan-P (preference-based HTN planning

Hierarchical task network

In artificial intelligence, the hierarchical task network, or HTN, is an approach to automated planning in which the dependency among actions can be given in the form of networks....

).

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 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

Starbucks

Starbucks Corporation is an international coffee and coffeehouse chain based in Seattle, Washington. Starbucks is the largest coffeehouse company in the world, with 17,009 stores in 55 countries, including over 11,000 in the United States, over 1,000 in Canada, over 700 in the United Kingdom, and...

 first and then continue to school. This increases the length of the plan but the user's preference is satisfied.

Planning Domain Definition Language

The Planning Domain Definition Language

Planning Domain Definition Language

The Planning Domain Definition Language is an attempt to standardize planning domain and problem description languages. It was developed mainly to make the 1998/2000 International Planning Competitions possible....

 (as of version 3.0) supports the specification of preferences through preference statements. For example, the statement

(preference (always (clean room1)))

indicates that the user prefers that room1 should be clean at each state of the plan. In other words, the planner should not schedule an action that causes room1 to become dirty. As this example shows, a preference is evaluated with regard to all states of a plan (if semantically

Semantics

Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....

 required).

In addition to always, other constructs based on linear temporal logic

Linear temporal logic

In logic, Linear temporal logic is a modal temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of paths such as that a condition will eventually be true, that a condition will be true until another fact becomes true, etc. It is a fragment of the more...

 are also supported, such as sometime (at least once during the plan), sometime-after (to be planned after a particular state) and at-most-once (the preference holds during at most one sequence of states in the plan).

Plan quality

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 is-violated which is equal to "the number of distinct preferences with the given name that are not satisfied in the plan". For a plan, a value can now be computed using a metric function, which is specified with :metric:

(:metric minimize (+ (* 5 (is-violated pref1)) (* 7 (is-violated pref2))))

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

Polish notation

Polish notation, also known as prefix notation, is a form of notation for logic, arithmetic, and algebra. Its distinguishing feature is that it places operators to the left of their operands. If the arity of the operators is fixed, the result is a syntax lacking parentheses or other brackets that...

. In this case, violation of the second preference has been given a greater penalty than the first preference.

Constraints satisfaction problem

In the area of constraint satisfaction problem

Constraint satisfaction problem

Constraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint...

s, flexible variants exist that deal with soft constraints in a similar way to preferences in preference-based planning.