Evolution of Planning in AI

Introduction

Planning is a critical part of AI where Agents can take advantage of the structure of a problem to construct complex plan of actions to achieve some goal. The path to reach the end goal consists of atomic facts (state variables) and actions make some facts true and some facts false. Given a description of the possible initial states of the world, a description of the desired goals, and a description of a set of possible actions, the planning problem is to find a plan that is guaranteed (from any of the initial states) to generate a sequence of actions that leads to one of the goal states

History of Planning

AI planning arose from investigations into state-space search, theorem proving, and control theory and from the practical needs of robotics, scheduling, and other domains. It all started when in 1959 Herbert Simon, J. C. Shaw and Allen Newell introduced a computer program called General Problem Solver which was intended to work as a universal problem solver.

In 1972, Allen Newell and Herbert Simon published the book Human Problem Solving, in which they outlined their problem space theory of problem solving. In this theory, people solve problems by searching in a problem space. The problem space consists of the initial (current) state, the goal state, and all possible states in between. The actions that people take in order to move from one state to another are known as operators. The problem spaces can be very large so the key issue is how people navigate their way through the possibilities, given their limited working memory capacities. In other words, how do they choose operators? For many problems, we possess domain knowledge that helps us decide what to do. But for novel problems Newell and Simon proposed that operator selection is guided by cognitive short-cuts, known as heuristics. The simplest heuristic is repeat-state avoidance or backup avoidance, whereby individuals prefer not to take an action that would take them back to a previous problem state. This introduction to Heuristics opened the door to many possibilities in Problem solving.

Planning Approaches

Logic/ Algorithmic based planning

During 1960’s till 1990 the popular planning techniques used were logic based and famous techniques used were Situational Calculus and Propositional Logic. Propositional Logic has been in existence since many centuries. There are many literatures that show the usage of Propositional Logic being used in ancient times. Its versions are revised by many scientist and it still exists today in more refined form. These techniques are still used in certain areas as they set as basis of modern Planning techniques. The further variants of Propositional Logic are First-Order logic, Second-order logic, higher-order logic that were introduced in the decade of 1990.

Partial Order Planning

Planners in the early 1970s generally considered totally ordered action sequences. Problem decomposition was achieved by computing a sub-plan for each sub-goal and then stringing the sub-plans together in some order. This approach, called linear planning by Sacerdoti (1975), was soon discovered to be incomplete due to the observed conflicts between sub-goals. Partial-order planning was introduced to resolve this conflict. Partial-Order planning dominated the next 20 years of research. Partial order planning fell out of favor in the late 1990s as faster methods emerged.

Graph Plan

Building a planning graph was popular during 1995-2000. In traditional approach for reaching a goal from initial state one will prepare a tree having arrangement of all the possible actions that lead to a goal. These trees can grow exponentially for complex problems. Graph Plan is polynomial sized approximation of these trees that can be constructed quickly. The planning graph can’t answer definitively whether Goal is reachable from initial state, but it can estimate how many steps it takes to reach Goal.

SATPlan

SATPlans (or Satisfiable Plan)were introduced in 1992 in a paper by Kautz and Selman. Kautz and Selman built a system that outperformed Game Plan and made SAT popular. There are multiple variants of SAT exist today. The SATPlan compiles a planning problem into logically satisfiability problem. Given a problem instance in planning, with a given initial state, a given set of actions, a goal, and a horizon length, a formula is generated so that the formula is satisfiable if and only if there is a plan with the given horizon length. The decreasing interest of planning researchers in SAT at this time can be traced to two factors: the impractically large size of the formulas generated from the standard benchmark problems with the early encoding schemes, and the very high computational cost of completing the satisfiability tests for horizon lengths shorter than the shortest plan.

Heuristic Search based Plans

Heuristics were introduced to overcome the shortcoming of previous approaches. Researchers observed that by calculating cost to reach the end goal at each stage and directing the Agent based on that was a major breakthrough in terms of problems that are unknown, unobservable or undeterministic. Some popular heuristics are critical path heuristics, ignoring deleted list, relaxed plan, landmark etc. Heuristics are used on graph searches are very effective in guaranteeing that we will reach the goal.

Other popular approaches

Some of the other popular approaches that are widely used based on the type of problem definitions are:

1.    Planning as first-order logical deduction: Situation calculus

2.   Planning as Constraint Satisfaction

3.   Planning as refinement of Partially-ordered plans

By Planning one can easily solve complex to complex problems. Planning approaches are evolving everyday. A committee called ICAPS (International Conference on Automated Planning and Scheduling) introduced International Planning Competition in 1998-2000 calling all the researchers in AI community to come in a common ground and rewarding the best Planning approach in terms of various parameters like satisfiability, completeness, optimality etc. For more information visit home page - http://icaps-conference.org/index.php/Main/Competitions

Planning Languages/ Frameworks

STRIPS

Stanford Research Institute (SRI) Scientists developed the first AI robot called “Shakey” in 1966. The robot used to perform a lot of basic operations like object identification, obstacle detection, reporting the problem state. The researchers at SRI took inspiration from general problem solving and theorem proving, and called the resulting algorithm “STRIPS”. STRIPS is often cited as providing a seminal framework for attacking the "classical planning problem" in which the world is regarded as being in a static state and is transformable to another static state only by a single agent performing any of a given set of actions. The planning problem is then to find a sequence of agent actions that will transform a given initial world state into any of a set of given goal states. For many years, automatic planning research was focused on that simple state-space problem formulation, and was frequently based on the representation framework and reasoning methods developed in the STRIPS system. Visit the flowing link to see the capability od Shakey - https://www.youtube.com/watch?v=qXdn6ynwpiI

ADL

Action Description Language or ADL was introduced as advancement of STRIPS in 1987 by Pednault. It is an automated planning and scheduling system in particular for robots. It relaxed some of the STRIP restrictions and made it possible to encode more realistic problems. The main change introduced was allowing the effects of an operator to be conditional.

PDDL

PDDL or Planning Domain Definition Language was introduced as an attempt to standardize Artificial Intelligence planning languages in 1998. It was inspired by STRIPS and ADL. PDDL is a language that carefully balances the expressiveness of the language with the complexity of the algorithms that operate on it. PDDL has many variants which were evolved over the last couple of decades to solve complex problems. E.g. PDDL+, NDDL, MAPL, OPT etc.

Conclusion

Planning combines the two major areas of AI: search and logic. A planner can be seen either as a program that searches for a solution or as one that (constructively) proves the existence of a solution. The cross-fertilization of ideas from the two areas has led both to improvements in performance amounting to several orders of magnitude in the last decade and to an increased use of planners in industrial applications. Unfortunately, we do not yet have a clear understanding of which techniques work best on which kinds of problems. Quite possibly, new techniques will emerge that dominate existing methods.

Planning research has been central to AI since its inception, and papers on planning are a staple of mainstream AI journals and conferences. There are also specialized conferences such as the International Conference on AI Planning Systems, the International Workshop on Planning and Scheduling for Space, and the European Conference on Planning

Reference

1.   Artificial Intelligence – A Modern Approach – by Stuart Russel and Peter Norvig

2.   AI Journal – STRIPS, a retrospective

3.   ICAPS website - http://icaps-conference.org/index.php/Main/Competitions

4.   PDDL - McDermott, Drew; Ghallab, Malik; Howe, Adele; Knoblock, Craig; Ram, Ashwin; Veloso, Manuela; Weld, Daniel; Wilkins, David (1998). "PDDL---The Planning Domain Definition Language" (PDF). Technical Report CVC TR98003/DCS TR1165. New Haven, CT: Yale Center for Computational Vision and Control.

5.   Action Description Language

6.   Propositional Logic - Chapter 2 / Propositional Logic from Logic In Action

7.   Situational Calculus - Lakemeyer, Gerhard. "The Situation Calculus and Golog: A Tutorial" (PDF). www.hybrid-reasoning.org. Retrieved 16 July 2014

#ai #artificialintelligence #shakey #plangraph #pddl #adl #situationalcalculus