Overview of automatic planning problems and reference books

Overview of automatic planning problems

An automatic programming problem is the problem of planning a sequence of actions necessary to achieve a certain goal. Specifically, it is an algorithm that determines the sequence of actions to start from a certain state and reach a target state. The automatic programming problem is widely used in fields such as artificial intelligence and robotics.

The automatic programming problem has the following elements.

• State Space: An automated programming problem is defined on a state space. A state space is the set of all possible states of a system. A state space can be a finite state space or an infinite state space.
• Action Space: In an automated programming problem, the set of actions taken to transition from one state to another is called the action space. An action space can be a finite action space or an infinite action space.
• Constraints: An automated programming problem may have constraints on actions. Examples of constraints are, for example, that some actions must precede other actions, or that certain actions cannot be performed in certain states.
• Objective Function: In an automated programming problem, it is required to minimize an objective function, such as the minimum cost or the minimum time to reach a target state.

There are various methods for automatic programming problems, such as state space search, inverse problem solving, and deep reinforcement learning, etc. In practice, it is important to select the best method for the problem in order to solve automatic programming problems. These methods are described below.

Various methods in automatic programming problems

Methods for solving the automatic planning problem include the following.

• State Space Search Method: The state space search method is effective when the state space is finite, and finds a plan to reach the target state by searching over the state space. Specific algorithms include width-first search, depth-first search, the A algorithm, and the IDA algorithm. The algorithms for state-space search systems are described below.

• • A Algorithm: The A algorithm will be one of the most commonly used automatic programming algorithms.The A* algorithm uses a heuristic function to search for the optimal solution for a given problem. Although this algorithm can be computationally time-consuming, it is generally capable of obtaining an optimal solution. For details of these tree search algorithms, see “Network Analysis Using Clojure (1) Width-first/Depth-first Search, Shortest Path Search, Minimum Spanning Tree, Subgraph and Connected Component” and “Basic Algorithms for Graph Data (DFS, BFS, Knee Graph Decision, Shortest Path Problem, Minimum Global Tree)” etc. for more information.
  • STRIPS algorithm: The STRIPS algorithm will be one of the automatic planning algorithms widely used in the field of artificial intelligence. The STRIPS algorithm is suitable for simple problems with relatively short computation time. For more information on inference algorithms, see “About Expert Systems and CLIPS” and “Backward and Forward Reasoning.
  • SAT solver: The SAT solver is an automated programming algorithm used in the field of propositional logic to solve the problem of determining whether a propositional logic formula is true or not, and in its application to automated programming problems, the SAT solver is used to solve constraint satisfaction problems. For more information on SAT, see “Overview and Implementation of SAT (Boolean SAtisfiability).
• Inverse Problem Solving: Inverse Problem Solving is effective when a target state is given, and the method is to find a plan that goes backwards from the target state to the initial state. This is done by the following procedure.

1. 1. Set the target state as the initial state.
   2. The actions to reach the initial state are applied in reverse according to the plan and the current state is updated.
   3. If the current state matches the initial state, exit assuming a plan has been found. If not, return to step 2.
   4. If no plan was found, the problem is unsolvable.

This approach is not suitable for large-scale problems because the computational complexity increases in proportion to the length of the plan. Memory usage can also be a problem, since information about the plan must be retained in order to proceed in the reverse direction of the plan.

• Randomized Search: Randomized search is a method of finding a plan to reach a target state by repeating random actions. Randomized search is a method of finding a plan to reach a target state by repeating random actions, such as random walk described in “Overview of Random Walks, Algorithms, and Examples of Implementations“, annealing, and genetic algorithms described in “Overview of genetic algorithms, application examples, and implementation examples“, which are heuristic algorithms as described in “The Mathematics of Metaheuristics: A Notebook“. Randomized search methods need to be careful about the possibility of falling into local solutions.
• Solving as an optimization problem: Some methods formulate the automatic programming problem as an optimization problem and solve it using optimization techniques. Specifically, linear programming described in “Overview of linear programming and examples of algorithms and implementations“, integer programming, nonlinear programming, etc. are used. The details of these methods are described in the section on the mathematics of optimization in “Mathematics in Machine Learning. They can also be formulated as optimization problems to address multi-objective optimization problems.
• Deep Reinforcement Learning: Deep Reinforcement Learning is a method that combines deep learning and reinforcement learning to find optimal plans by learning neural networks for action decisions. The application of deep reinforcement learning to automatic planning has been attracting attention in recent years as an effective method when the state space or action space is large. For details of deep reinforcement learning, please refer to “Theories and Algorithms of Various Reinforcement Learning Techniques and Their Python Implementations“.

Libraries and Platforms Used for Automated Programming Problems

There are various libraries and platforms that can be used to tackle automated programming problems. Some of them are described below.

• PDDL (Planning Domain Definition Language): PDDL is a general language for expressing automated planning problems; libraries and tools that support PDDL can help you perform tasks such as modeling problems, generating plans, and analyzing plans.
• Fast Downward: Fast Downward is an open source planning framework that implements efficient planning algorithms, supports PDDL, and supports plan generation in various domains.
• STRIPS: STRIPS (Stanford Research Institute Problem Solver) is a classic framework for solving automated planning problems. ROS (Robot Operating System)
• ROS (Robot Operating System): ROS is a flexible and powerful platform for developing robotic applications. ROS provides libraries and tools related to automatic planning and to solve problems such as robot movement planning, task scheduling, etc. It is used for.
• PDDL4J: PDDL4J will be a library that supports the parsing and manipulation of PDDL (Planning Domain Definition Language) written in Java. PDDL4J can read PDDL files, define problems, generate plans, and perform various PDDL4J can be used to perform a variety of PDDL-related tasks, such as reading PDDL files, defining problems, and generating plans.

Next, we discuss some applications of automated programming.

Application examples of automatic programming methods

Automatic programming problems are used in many fields. Typical applications are described below.

• Scheduling: One of the most popular applications of the automatic programming problem is to the scheduling problem. This can be, for example, the scheduling of manufacturing processes or the scheduling of meetings in an office.
• Robot Control: The automatic planning problem has applications in robot motion planning and task planning. This could be, for example, motion planning for an autonomous mobile robot in a factory or task planning for a transport robot in a distribution center.
• Game AI: The automatic planning problem is also used in the field of game AI, as described in “Basic Technologies of Digital Game AI (Temporal Aesthetics): Past Memory, Future (Planning)“. For example, in board games such as chess and shogi, the problem of considering the next best move is an automatic planning problem, and in real-time strategy games, it can be used to plan unit movements, attacks, and other actions.
• Cognitive Robotics: Automated programming problems are also used in the field of cognitive robotics. This could be, for example, planning the movement of an arm to grasp an object on a desk based on visual information, or planning actions to achieve collaboration with a human.
• Automated Driving: The automatic planning problem also has applications in automated driving technology. This would be, for example, trajectory planning and speed control of a vehicle.

Implementation in python

There are several libraries for Python-based implementations of automated programming. Here we describe a Python implementation of automatic programming using pyperplan, a library for solving problems written in the form of PDDL. First, install the pyperplan library.

>pip install pyperplan

Next, create a PDDL file. 

PDDL (Planning Domain Definition Language) is one of the formal languages used for automated planning in the field of artificial intelligence, a standard description language for describing planning domains and problems, and one that many automated planning systems support PDDL PDDL is a standard description language for describing planning domains and problems.

PDDL allows the definition of the state, initial state, actions, goal state, etc. of a planning problem, and the domain description has language elements for defining actions, state variables, constraints, etc. Problem descriptions include concrete states, goal states, and available objects.

(define (problem sample)
  (:domain sample-domain)
  (:objects a b c)
  (:init (on a b) (on b c) (clear a) (clear c))
  (:goal (and (on a c) (on c b))))

The above PDDL file has the goal of having three objects, a, b, and c, in a domain named the sample domain, starting with a on top of b, b on top of c, and both a and c free, so that a is on top of c and c is on top of b. Next, we create the Python code.

from pyperplan import Plan
from pyperplan.planning import AbstractTask, Task
from pyperplan.search import AStar
from pyperplan.propositional_planner import PropositionalPlanner
from pyperplan.heuristics import BlindHeuristic

# Read PDDL file
domain_file = 'sample-domain.pddl'
problem_file = 'sample-problem.pddl'

# Create an object representing the problem
task = Task(domain_file, problem_file)

# Create a search algorithm to solve the problem
search_algorithm = AStar()

# Create a planner to solve problems
planner = PropositionalPlanner(task, search_algorithm, BlindHeuristic())

# solve a problem
plan = planner.plan()

# Show Plans
for action in plan:
    print(action.name)

The above Python code will use the pyperplan library to solve the problem represented by the PDDL file we just created and display the plan. In addition to this, python has other libraries for automatic planning methods such as FF and Fast-Downward.

Implementation in Clojure

Automated programming can also be implemented in functional languages such as Clojure. clj-planning, a library for solving PDDL-style problems, is available in Clojure. In the following, we show an example of a Clojure implementation of an automatic programming method using clj-planning. First, add the clj-planning library to your project.

;; When using Leiningen
[clj-planning "0.4.0"]

Next, a PDDL file is created as in the pyhton case described above.

(define (problem sample)
  (:domain sample-domain)
  (:objects a b c)
  (:init (on a b) (on b c) (clear a) (clear c))
  (:goal (and (on a c) (on c b))))

The above PDDL file has the goal of having three objects, a, b, and c, in a domain named Sample Domain, starting with a on top of b, b on top of c, and both a and c free, so that a is on top of c and c is on top of b. Next, we create the Clojure code.

(ns my-project.core
  (:require [clj-planning.core :as planning]))

;; Read PDDL file
(def domain-file "sample-domain.pddl")
(def problem-file "sample-problem.pddl")

;; solve a problem
(let [task (planning/task-from-files domain-file problem-file)
      plan (planning/plan task)]
  ;; Show Plans
  (doseq [action plan]
    (println (:name action))))

The above Clojure code uses the clj-planning library to solve the problem represented by the PDDL file we just created and display the plan. STRIPS and Fast Downward.

These basic concepts were developed in LISP in the past; see also “Practical Common Lisp Reading Notes” for more details.

reference book (work)

Foundational & Comprehensive Texts

1. Automated Planning: Theory and Practice
   Malik Ghallab, Dana Nau, Paolo Traverso
   Morgan Kaufmann, 2004

   • A classic, systematic textbook covering STRIPS, HTN, PDDL, and planning algorithms in detail.

2. Planning Algorithms
   Steven M. LaValle
   Cambridge University Press, 2006 (free online version available)

   • A broad coverage of planning algorithms, including motion planning, discrete planning, uncertainty, and robotics.

3. Automated Planning and Acting
   Malik Ghallab, Dana Nau, Paolo Traverso
   Cambridge University Press, 2016

   • An updated and extended version of their earlier work, adding reactive planning, execution monitoring, and integration with acting.

Advanced & Specialized Topics

4. Principles of Artificial Intelligence Planning
   Michael Ghallab, Craig Knoblock (Eds.)

   • Covers classical AI planning as well as specialized and emerging topics in the field.

5. Articles on Automated Planning and Scheduling, Including: Planner (Programming Language), Deterministic Policy, Planning Domain Definition Language, Strips, Graphplan, Multi-Agent Planning, Satplan, Hierarchical Task Network 

6. Temporal Planning
   Daniele Magazzeni, Enrico Scala

   • Focuses on planning with temporal and resource constraints.

General AI Texts with Planning Coverage

7. Artificial Intelligence: A Modern Approach (3rd Edition)
   Stuart Russell, Peter Norvig

   • A comprehensive AI textbook with chapters on classical planning, partial-order planning, and decision-theoretic planning.

8. Automated Planning and Scheduling