AI Planning - The travelling salesman problem

the following three papers have made significant difference in the AI field of planning and problem-solving.

The DPLL, though 50 years old - is still the basis for most SAT solvers. SAT Solvers are very useful for solving hard problems, one example in software verification - where you represent your model as a set of formulas, and the condition you want to verify - and invoke the SAT solver over it. Although exponential worst case - the average case is fast enough and is widely used in the industry (mainly for verifying Hardware components).

The STRIPS revolutionized planning with the introduction of a simple language to easily represent the world states, object, actions with prerequisites and effects and goal states.

The big introduction of Graphplan is that this is a propositional planner, this means that there are no variables floating around during the planning process and that the planner is simpler but bigger due to the use propositions instead of variables to describe the world.

DPLL algorithm

Davis, Martin; Logemann, George; Loveland, Donald, "A Machine Program for Theorem Proving". Communications of the ACM. 5 (7): 394–397, (1962)

Davis Martin, Logeman George and Loveland Donald developed this algorithm in 1962 to help proofing theorems of quantification theory.

The basic backtracking algorithm runs by choosing a literal, assigning a truth value to it, simplifying the formula and then recursively checking if the simplified formula is satisfiable; if this is the case, the original formula is satisfiable; otherwise, the same recursive check is done assuming the opposite truth value. This is known as the splitting rule, as it splits the problem into two simpler sub-problems. The simplification step essentially removes all clauses that become true under the assignment from the formula and all literals that become false from the remaining clauses.

The DPLL algorithm enhances the backtracking algorithm by the eager use of the following rules at each step:

• Unit propagation

  If a clause is a unit clause, i.e. it contains only a single unassigned literal, this clause can only be satisfied by assigning the necessary value to make this literally true. Thus, no choice is necessary. In practice, this often leads to deterministic cascades of units, thus avoiding a large part of the naive search space.

• Pure literal elimination

  If a propositional variable occurs with only one polarity in the formula, it is called pure. Pure literals can always be assigned in a way that makes all clauses containing them true. Thus, these clauses do not constrain the search anymore and can be deleted.

Unsatisfiability of a given partial assignment is detected if one clause becomes empty, i.e. if all its variables have been assigned in a way that makes the corresponding literals false. Satisfiability of the formula is detected either when all variables are assigned without generating the empty clause. Unsatisfiability of the complete formula can only be detected after an exhaustive search.

STRIPS

Richard E. Fikes, Nils J. Nilsson. "STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving”, (Winter 1971)

Richard E. Fikes and Nils J. Nilsson developed this revolutionary approach to problem-solving by creating this automated planning and it's also the name of the formal language, this is still used in planning today.

A STRIPS instance is composed of:

• An initial state (the problem space)

• the specification of the goal states – situations which the planner is trying to reach

• A set of actions. For each action, the following are included: preconditions (what must be established before the action is performed) postconditions (what is established after the action is performed)

For a very simple problem a search strategy similar to breath first search can be effective but if the world state is complex the state space can grow quickly and become impractical.

STRIPS adopts the GPS strategy of extracting "differences" between the present world model and the goal and of identifying operators that are "relevant" to reducing these differences.

Once a relevant operator has been determined, it attempts to solve the subproblem of producing a world model to which it is applicable. If such a model is found, then it applies the relevant operation and is considered the original goal in the resulting model.

GRAPHPLAN

A. Blum and M. Furst, "Fast Planning Through Planning Graph Analysis", Artificial Intelligence, 90:281--300 (1997)

Graphplan is a general-purpose planner for STRIPS-style domains based on ideas used in graph algorithms.

Given a problem statement, it explicitly constructs and annotates a compact structure called a Planning Graph, in which a plan is a kind of "flow" of truth-values through the graph. This graph has the property that useful information for constraining search can quickly be propagated through the graph as it is being built. Graphplan then exploits this information in the search for a plan.

In the state space graph:

• the nodes are possible states

• the edges indicate reachability through a certain action

On the contrary, in Graphplan's planning graph:

• the nodes are actions and atomic facts, arranged into alternate levels.

• the edges are of two kinds:

  from an atomic fact to the actions for which it is a condition.

  from action to the atomic facts it makes true or false.

Conclusion

The performance of the GraphPlan algorithm is no longer state of the

art, but the algorithm is the foundation of more modern approaches and is still relevant today.

If you find this article interesting please join our mailing list to not miss any update and schedule a free no obligation meeting with us to discuss your Analytics and AI needs.

Cheers, Andrea