Overview of automatic planning problems and reference books

Machine Learning Artificial Intelligence Natural Language Processing Artificial Intelligence Algorithm Artificial Life and Agent Reasoning Technology Knowledge Information ICT Technology Digital Transformation Automata and Automatic Planning  Navigation of this blog
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.
      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, 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
    

    コメント

    Exit mobile version
    タイトルとURLをコピーしました