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.
-
- Set the target state as the initial state.
- The actions to reach the initial state are applied in reverse according to the plan and the current state is updated.
- If the current state matches the initial state, exit assuming a plan has been found. If not, return to step 2.
- 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, 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, 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)
A reference book on automated planning is “Automated Planning Theory and Practice.
It reflects this dialogue by providing a comprehensive and up-to-date resource on the theory and practice of automated planning. It will be a reference book that goes beyond classical planning to include temporal planning, resource scheduling, planning under uncertainty, and the latest techniques for plan generation, including task decomposition, proposition satisfiability, constraint satisfaction, and model checking.
The contents are listed below.
Automated Palnning theory and practices Chapter 1 Introduction and Overview 1.1 First Intuitions on Planning 1.2 Forms of Planning 1.3 Domain-independent Planning 1.4 Conceptual Model for Planning 1.5 Restricted Model 1.6 Extended Models 1.7 A Running Example:Dock-Worker Robots Part 1 Classical Planning Chapter 2 Representations for Classical Planning 2.1 Introduction 2.2 Set-Theoretic Representations 2.2.1 Planning Domain, Problems, and Solutions 2.2.2 State Reachability 2.2.3 Starting a Planning Problem 2.2.4 Properties of the Set-Theoretic Representation 2.3 Classical Representation 2.3.1 States 2.3.2 Operators and Actions 2.3.3 Plans, Problems, and Solutions 2.3.4 Semantics of Classical Representations 2.4 Extending the Classical Representation 2.4.1 Simple Syntactical Extensions 2.4.2 Conditional Planning Operations 2.4.3 Quantified Expressions 2.4.4 Disjunctive Preconditions 2.4.5 Axiomatic Inference 2.4.6 Function Symbols 2.4.7 Attached Procedures 2.4.8 Extended Goal 2.5 State-Variable Representation 2.5.1 State Variables 2.5.2 Operators and Actions 2.5.3 Domains and Problems 2.5.4 Properties 2.6 Comparisons 2.7 Discussion and Historical Remarks 2.8 Exercise Chapter 3 Complexy of Classical Planning 3.1 Introduction 3.2 Preliminaries 3.3 Decidability and Undecidability Results 3.4 Complexity Results 3.4.1 Binary Counters 3.4.2 Unrestricted Classical Planning 3.4.3 Other Results 3.5 Limitations 3.6 Discussion and Historical Remarks 3.7 Exercises Chapter 4 State-Space Planning 4.1 Introduction 4.2 Forward Search 4.2.1 Formal Properties 4.2.2 Deterministic implementations 4.3 Backward Search 4.4 The STRIPS Algorithm 4.5 Domain-Specific Sates-Space Planning 4.5.1 The Container-Stacking Domain 4.5.2 Planning Algorithm 4.6 Discussion and Historical Remarks 4.7 Exercises Chapter 5 Plan-Space Planning 5.1 Introduction 5.2 The Search Space of Partial Plans 5.3 Solution Plans 5.4 Algorithms for plan-Space Planning 5.4.1 The PSP Procedure 5.4.2 The PoP Procedure 5.5 Extensions 5.6 Plan-Space versus State-Space Planning 5.7 Discussions and Historical Planning 5.8 Exercises Part 2 Neoclassical Planning Chapter 6 Planning-Graph Technique Chapter 7 Probabilistic Satisfiability Technique Chapter 8 Constraint Satisfaction Techniques Part 3 Heuristics and Control Startegies Chapter 9 Heuristic in Planning Chapter 10 Control Rules in Planning Chapter 11 Hierarchical Task Network Planning Chapter 12 Control Strategies in Deductive Planning Part 4 Planning with Time and Resources Chapter 13 Time for Planning Chapter 14 Temporal Planning Chapter 15 Planning and Resources Scheduling Part 5 Planning under Uncertainty Chapter 16 Planning Based on Markov Decu¥vision Processing Chapter 17 Planning Based on Model Checking Chapter 18 Uncertainty with Neoclassical Techniques Part 6 Case Studies and Applications Chapter 19 Space Applications Chapter 20 Planning in Robotics Chapter 21 Planning for Manufacturability Analysis Chapter22 Emergency Evacuation Planning Chapter 23 Planning ih the Game of Bridge Part 7 Conclusion Chapter 24 Other Approach to Planning Part 8 Appendices Appendix A Appendix B Appendix C
コメント