Artificial Intelligence Tutorial

Introduction to Artificial Intelligence Intelligent Agents

Search Algorithms

Problem-solving Uninformed Search Informed Search Heuristic Functions Local Search Algorithms and Optimization Problems Hill Climbing search Differences in Artificial Intelligence Adversarial Search in Artificial Intelligence Minimax Strategy Alpha-beta Pruning Constraint Satisfaction Problems in Artificial Intelligence Cryptarithmetic Problem in Artificial Intelligence

Knowledge, Reasoning and Planning

Knowledge based agents in AI Knowledge Representation in AI The Wumpus world Propositional Logic Inference Rules in Propositional Logic Theory of First Order Logic Inference in First Order Logic Resolution method in AI Forward Chaining Backward Chaining Classical Planning

Uncertain Knowledge and Reasoning

Quantifying Uncertainty Probabilistic Reasoning Hidden Markov Models Dynamic Bayesian Networks Utility Functions in Artificial Intelligence

Misc

What is Artificial Super Intelligence (ASI) Artificial Satellites Top 7 Artificial Intelligence and Machine Learning trends for 2022 8 best topics for research and thesis in artificial intelligence 5 algorithms that demonstrate artificial intelligence bias AI and ML Trends in the World AI vs IoT Difference between AI and Neural Network Difference between Artificial Intelligence and Human Intelligence Virtual Assistant (AI Assistant) ARTIFICIAL INTELLIGENCE PAINTING ARTIFICIAL INTELLIGENCE PNG IMAGES Best Books to learn Artificial Intelligence Certainty Factor in AI Certainty Factor in Artificial Intelligence Disadvantages of Artificial Intelligence In Education Eight topics for research and thesis in AI Engineering Applications of Artificial Intelligence Five algorithms that demonstrate artificial intelligence bias 6th Global summit on artificial intelligence and neural networks Acting Humanly In Artificial Intelligence AI and ML Trends in the World AI vs IoT Artificial Communication Artificial intelligence assistant operating system Artificial Intelligence in Pharmacy Artificial Intelligence in Power Station Artificial Intelligence in Social Media Artificial Intelligence in Supply Chain Management Artificial Intelligence in Transportation Artificial Intelligence Interview Questions and Answers Artificial Intelligence Jobs in India For Freshers Integration of Blockchain and Artificial Intelligence Interesting Facts about Artificial Intelligence Machine Learning and Artificial Intelligence Helps Businesses Operating System Based On Artificial Intelligence SIRI ARTIFICIAL INTELLIGENCE SKILLS REQUIRED FOR ARTIFICIAL INTELLIGENCE Temporal Models in Artificial Intelligence Top 7 Artificial Intelligence and Machine Learning trends for 2022 Types Of Agents in Artificial Intelligence Vacuum Cleaner Problem in AI Water Jug Problem in Artificial Intelligence What is Artificial Super Intelligence (ASI) What is Logic in AI Which language is used for Artificial Intelligence Essay on Artificial Intelligence Upsc Flowchart for Genetic Algorithm in AI Hill Climbing In Artificial Intelligence IEEE Papers on Artificial Intelligence Impact of Artificial Intelligence On Everyday Life Impact of Artificial Intelligence on Jobs

Classical Planning

Classical Planning is the planning where an agent takes advantage of the problem structure to construct complex plans of an action. The agent performs three tasks in classical planning:

  • Planning: The agent plans after knowing what is the problem.
  • Acting: It decides what action it has to take.
  • Learning: The actions taken by the agent make him learn new things.
Classical Planning

A language known as PDDL(Planning Domain Definition Language) which is used to represent all actions into one action schema.

PDLL describes the four basic things needed in a search problem:

  • Initial state: It is the representation of each state as the conjunction of the ground and functionless atoms.
  • Actions: It is defined by a set of action schemas which implicitly define the ACTION() and RESULT() functions.
  • Result: It is obtained by the set of actions used by the agent.
  • Goal: It is same as a precondition, which is a conjunction of literals (whose value is either positive or negative).

There are various examples which will make PDLL understandable:

  • Air cargo transport
  • The spare tire problem
  • The blocks world and many more.

Let’s discuss one of them

  • Air cargo transport

 This problem can be illustrated with the help of the following actions:

  • Load: This action is taken to load cargo.
  • Unload: This action is taken to unload the cargo when it reaches its destination.
  • Fly: This action is taken to fly from one place to another.

Therefore, the Air cargo transport problem is based on loading and unloading the cargo and flying it from one place to another.

Below is the PDLL description for Air cargo transport:

Init (On(C1, SFO) ?  On(C2, JFK) ?  On(P1, SFO) ? On(P2, JFK)? Cargo(C1) ? Cargo(C2) ? Plane(P1) ? Plane(P2)
? Airport (JFK) ?  Airport (SFO))
Goal (On(C1, JFK) ?  On(C2, SFO))
Action(Load (c, p, a),
PRECOND: On(c, a) ? On(p, a) ? Cargo(c) ? Plane(p) ? Airport (a)
EFFECT: ? On(c, a) ? In(c, p))
Action(Unload(c, p, a),
PRECOND: In(c, p) ? On(p, a) ? Cargo(c) ? Plane(p) ? Airport (a)
EFFECT: On(c, a) ? ?In(c, p))
Action(Fly(p, from, to),
PRECOND: On(p, from) ? Plane(p) ? Airport (from) ? Airport (to)
EFFECT: ? On(p, from) ?  On(p, to)) 

The above described actions, (i.e., load, unload, and fly) affects the following two predicates:

  • (c,p): In this, the cargo is inside the plane p.
  • (x,a): In this, the object x is at the airport a. Here, object can be the cargo or plane.

It is to be noted that when the plan flies from one place to another, it should carry all cargo inside it. It becomes difficult with the PDLL to give solution for such a problem. Because PDLL do not have the universal quantifier. Thus, the following approach is used:

  • piece of cargo ceases to beOn anywhere when it is In a plane.
  • the cargo only becomesOn the new airport when it is unloaded.

Therefore, the planning for the solution is:

 Load (C1, P1, SFO), Fly(P1, SFO, JFK),Unload(C1, P1, JFK),
 Load (C2, P2, JFK), Fly(P2, JFK, SFO),Unload(C2, P2, SFO)] . 

Note: Some problems can be ignored because they does not cause any problem in planning.

  • The spare tire problem

The problem is that the agent needs to change the flat tire. The aim is to place a good spare tire over the car’s axle. There are four actions used to define the spare tire problem:

  1. Remove the spare from the trunk.
  2. Remove the flat spare from the axle.
  3. Putting the spare on the axle.
  4. Leave the car unattended overnight. Assuming that the car is parked at an unsafe neighborhood.

The PDLL description for the spare tire problem is:

Init(Tire1(Flat ) ? Tire1(Spare) ? At(Flat , Axle) ? At(Spare, Trunk ))
Goal (At(Spare, Axle))
Action(Remove(obj , loc),
PRECOND: At(obj , loc)
EFFECT: ? At(obj , loc) ? At(obj , Ground))
Action(PutOn(t , Axle),
PRECOND: Tire1(t) ? At(t , Ground) ?¬At(Flat , Axle)
EFFECT: ? At(t , Ground) ? At(t , Axle))
Action(LeaveOvernight ,
PRECOND:
EFFECT: ? At(Spare, Ground) ?¬At(Spare, Axle) ?¬At(Spare, Trunk)
?¬At(Flat, Ground) ?¬At(Flat , Axle) ?¬At(Flat, Trunk)) 

 The solution to the problem is:

[Remove(Flat,Axle),Remove(Spare,Trunk), PutOn(Spare, Axle)].

Similarly, we can design PDLL for various problems.

Complexity of the classical planning

In classical planning, there occur following two decision problems:

  1. PlanSAT: It is the question asking if there exists any plan that solves a planning problem.
  2. Bounded PlanSAT: It is the question asking if there is a solution of length k or less than it.

We found that:

  • PlanSAT and Bounded PlanSAT are decidable for classical planning.
  • Both decision problems lie in the complexity class PSPACE, which is larger than NP.

Note: PSPACE is the class which refers to those problems that can be solved via deterministic Turing machine under a polynomial time space.

From the above, it can be concluded that:

  1. PlanSAT is P whereas Bounded PlanSAT is NP-complete.
  2. Optimal planning is hard with respect to sub-optimal planning.

Advantages of Classical Planning

There are following advantages of Classical planning:          

  • It has provided the facility to develop accurate domain-independent heuristics.
  • The systems are easy to understand and work efficiently.