Planning and learning

Module 6
Planning
● Artificial Intelligence (AI) is reshaping the future, playing a pivotal role in
domains like intelligent robotics, self-driving cars, and smart cities.
● At the heart of AI systems’ ability to perform tasks autonomously is AI
planning, which is critical in guiding AI systems to make informed decisions,
execute tasks, and achieve goals efficiently.
● In Artificial Intelligence (AI), planning refers to the process of deciding a
sequence of actions that a system must take to achieve a specific goal
starting from a initial state. Just like humans plan their daily tasks with a goal
in mind, AI systems use planning algorithms to break down a problem into
smaller, manageable tasks and determine the best course of action.
● It is a crucial area of AI, especially in robotics, game playing, automated
reasoning, and decision support systems.
What is AI Planning?
AI planning is the automated process of generating a plan—a series of actions—with the goal of
achieving a desired outcome from a known starting point, given constraints and a model of the
environment.

● Initial State: The current condition or situation the agent is in.

● Goal State: The desired condition the agent aims to reach.

● Actions: Steps the agent can take to move from one state to another.

● Plan: A sequence of actions that leads from the initial state to the goal state.
Planning
Planning is crucial for AI applications because it allows machines to:

● Think ahead: AI systems evaluate multiple possible outcomes before selecting

the optimal one.
● Adapt to changes: When faced with uncertain environments, AI systems can
revise their plans based on new information.
● Act autonomously: Whether it’s an autonomous robot or a smart assistant, AI
planning enables machines to perform tasks independently.
Components of a Planning System
Component Description

State A representation of the environment at a specific time.

Actions (Operators) Defined by preconditions (when they can be executed) and
effects (how they change the state).
Transition Model Describes how actions transform one state into another.
Goal Test Determines if a given state satisfies the goal conditions.
Plan An ordered or partially ordered set of actions to achieve the
goal.
Types of Planning in AI
A. Classical Planning
● Assumes the world is fully observable, deterministic, static, and discrete.
● Uses STRIPS (Stanford Research Institute Problem Solver) or PDDL (Planning Domain Definition
Language).
● Example: Chess playing, route finding.

B. Partial-Order Planning
● Actions do not have to be in a total linear order; some actions can be unordered if they don't
interfere.
● Useful for parallel execution.
● Example: Cooking (you can boil water and chop vegetables simultaneously).

C. Hierarchical Planning (HTN - Hierarchical Task Networks)

● Breaks high-level goals into simpler sub-goals or tasks.
● Useful for complex tasks with multiple abstraction levels.
● Example: “Travel to New York” → “Book flight”, “Pack bags”, “Go to airport”.
Types of Planning in AI
D. Conditional Planning
● Accounts for uncertainty by planning contingencies.
● Includes if-then-else branches.
● Example: If it rains, carry an umbrella; else, wear sunglasses.

E. Probabilistic Planning
● Uses probabilities to deal with uncertain outcomes of actions.
● Often represented using Markov Decision Processes (MDPs) or Partially Observable MDPs
(POMDPs).
● Example: Robot navigation where the environment may have moving obstacles.

F. Temporal Planning
● Considers time durations and deadlines for actions.
● Example: A satellite scheduling observations where time windows are critical.
https://www.youtube.com/watch?v=Ng6zy7hI64A
Planning Algorithms
a. Forward State-Space Search
● Starts from the initial state and searches forward through the state space until the goal is found.

b. Backward Search (Goal Regression)

● Starts from the goal state and searches backward to the initial state.

c. GraphPlan
● Builds a planning graph that represents how actions and states are related over time.

d. Heuristic Search in Planning

● Uses heuristic functions to estimate cost/distance to goal (e.g., A*, Greedy search).

Planning vs. Scheduling

● Planning: Decides what actions to perform.
● Scheduling: Decides when and how to perform those actions considering time/resources.
Two Major Approaches to Planning
1. Total-Order Planning (TOP)

A planning strategy where all actions are totally ordered—that is, they are arranged in a fixed linear sequence. Every
action must be performed in a specific order.
Features:
● Actions are executed strictly one after another.
● Simpler but less flexible.
● Easier to implement and debug.
● Cannot leverage concurrency.

Example: Task: Make tea.

Plan (TOP):
1. Boil water
2. Add tea leaves
3. Pour into cup
4. Add sugar

Even if some steps are independent, they must follow the exact order.

Use Case:
Useful in deterministic and serial environments (e.g., assembly lines).
Two Major Approaches to Planning
2. Partial-Order Planning (POP)
A planning strategy that allows actions to be partially ordered—only constraining actions when necessary due to precondition or causal
dependencies.

Features:
● Also called Least Commitment Planning.
● Only required actions are ordered.
● Allows parallelism and flexibility.
● Plans are more compact and reusable.

Example: Task: Prepare breakfast (tea + toast).

Plan (POP):
● Boil water → Pour tea
● Toast bread → Apply butter

Here, boiling water and toasting bread can occur in parallel, since they are independent.
Only necessary orderings are enforced:
● You must toast bread before applying butter.
● You must boil water before pouring tea.

Use Case:
Ideal for multi-agent systems, robotics, or workflows where some actions can occur in parallel.
 Total-Order Planning (TOP) Vs Partial-Order Planning (POP)

Feature Total-Order Planning (TOP) Partial-Order Planning (POP)

Action Order Fully ordered Only partially ordered

Flexibility Low High

Concurrency Not supported Supported

Plan Representation Linear sequence DAG (Directed Acyclic Graph)

Alternative Names Linear Planning Least Commitment Planning

Planning Strategy Commit to sequence early Delay commitment until

necessary

Execution Strictly sequential Parallelizable if possible

Applications of Planning in AI

Domain Application Example

Robotics Path and task planning for autonomous robots.

Games Strategy planning in AI opponents.
Logistics Delivery routing, cargo loading.
Space Exploration NASA’s Mars rovers use planning systems.
Healthcare Treatment planning and appointment scheduling.
Smart Assistants Planning meetings or daily routines.
 Learning
Types of Learning in Artificial Intelligence (AI)
Artificial Intelligence (AI) learns from data and experiences to improve
decision-making

Types:

● Supervised Learning
● Unsupervised Learning
● Semi-Supervised Learning
● Reinforcement Learning
● Ensemble learning
What is machine learning?

● A branch of artificial intelligence, concerned with the

design and development of algorithms that allow
computers to evolve behaviors based on empirical data.

● As intelligence requires knowledge, it is necessary for the

computers to acquire knowledge
What is machine learning?

● Machine Learning takes advantage of the ability of computer

systems to learn from correlations hidden in the data; this ability
can be further utilized by programming or developing intelligent
and efficient Machine Learning algorithms.
● They use computational methods to “learn” information directly
from data without relying on a predetermined equation as a
model.
● As the number of samples available for learning increases,
machine learning algorithms adaptively improve their
performance.
What is machine learning?

● Machine Learning
¨Study of algorithms that improve their performance ¨at some task ¨with experience
● Optimize a performance criterion using example data or past
experience.
● Role of Statistics: Inference from a sample
● Role of Computer science: Efficient algorithms to
❖ Solve the optimization problem
❖ Representing and evaluating the model for inference
What is machine learning?
Machine learning vs. “classic” programming.

Sebastian Raschka:Intro to Machine Learning

What is machine learning?
Arthur Samuel (1959)

● Machine learning: "Field of study that gives computers the ability to learn without
being explicitly programmed"
○ Samuels wrote a checkers playing program
■ Had the program play 10000 games against itself
■ Work out which board positions were good and bad depending on wins/losses

Tom Michel (1999)

● Well posed learning problem: "A computer program is said to learn from experience
E with respect to some class of tasks T and performance measure P, if its
performance at tasks in T, as measured by P, improves with experience E."
○ The checkers example,
■ E = 10000s games
■ T is playing checkers
■ P if you win or not
Definition of learning
Definition: A computer program is said to learn from experience E with respect to
some class of tasks T and performance measure P, if its performance at tasksT, as
measured by P, improves with experience E.

Examples Inducting Learning: Learning from experience

i) Handwriting recognition learning problem

• Task T: Recognising and classifying handwritten words within images

• Performance P: Percent of words correctly classified

• Training experience E: A dataset of handwritten words with given classifications

Machine - Learning - Tom Mitchell.

Definition of learning
ii) A robot driving learning problem
• Task T: Driving on highways using vision sensors
• Performance measure P: Average distance traveled before an error
• Training experience: A sequence of images and steering commands recorded while
observing a human driver
iii) A chess learning problem
• Task T: Playing chess
• Performance measure P: Percent of games won against opponents
• Training experience E: Playing practice games against itself

Machine - Learning - Tom Mitchell.

Types of Machine Learning

Supervised Learning :Teach the computer how to do something, then let it use
it;s new found knowledge to do it
In supervised learning, the computer is provided with example inputs that
are labeled with their desired outputs.
The purpose of this method is for the algorithm to be able to “learn” by
comparing its actual output with the “taught” outputs to find errors, and
modify the model accordingly.
Supervised learning therefore uses patterns to predict label values on
additional unlabeled data.
Types of Machine Learning
Types of Machine Learning
Types of Machine Learning
Unsupervised Learning: Let the computer learn how to do something, and
use this to determine structure and patterns in data

In unsupervised learning, data is unlabeled, so the learning algorithm is left to find

commonalities among its input data
Types of Machine Learning
Types of Machine Learning
Types of Machine Learning
Reinforcement learning
● Reinforcement learning (RL) is important for “strategy learning”. It
is useful for robotics, for playing games, etc.
● The well-known alpha-GO actually combined RL with deep
learning, and was the first program that defeated human expert
Go-players.
● In RL, a learner is called an agent. The point is to take a
correct “action” for each environment “situation”.
● If there is a teacher who can tell the correct actions for all
situations, we can use supervised learning.
● In RL, we suppose that the teacher only “rewards” or
“punishes” the agent under some (not all) situations.
Machine Learning: Produced by Qiangfu Zhao
Reinforcement learning
● RL can find a “map” (a Q-table) that defines the relation between the situation set
and the action set, so that the agent can get the largest reward by following this
map.
● To play a game successfully, the computer can generate many different situations,
and find a map between situation set and action set in such a way to win the
game (with a high probability).
● Thus, even if there is no human opponent, a machine can improve its skill by
playing with itself, using RL.
● Of course, if the machine has the honor to play many games with human experts,
it can find the best strategy more “efficiently” without generating many
“impossible” situations; or find good computer game players more acceptable to
human.
● Examples: playing backgammon or chess, scheduling jobs, and controlling robot
limbs
Machine Learning: Produced by Qiangfu Zhao
Applications
Robotics
● RL helps robots learn complex tasks like walking, grasping objects, and
autonomous navigation.

Game Playing
● AlphaGo and AlphaZero use RL to achieve superhuman performance in Go and
Chess.

Autonomous Vehicles
● RL-based policies help self-driving cars navigate safely in dynamic environments.

Healthcare
● Personalized treatment recommendations based on patient response to
medications
Semi Supervised Learning
In Semi supervised learning, some input data is labeled and some is unlabeled.
Classification
In machine learning, classification is the problem of identifying to which of a set of
categories a new observation belongs, on the basis of a training set of data
containing observations (or instances) whose category membership is known.
Example 1
Consider the following data: -training set of data.
-two attributes “Score1” and “Score2”.
-class label is called “Result”.
-class label has two possible values
“Pass” and “Fail”.
-The data can be divided into two
categories or classes:
Classification
If we have some new data, say “Score1 =
25” and “Score2 = 36”, what value should be
assigned to “Result” corresponding to the
new data; in other words, to which of the two
categories or classes the new observation
should be assigned?
To answer this question, using the given
data alone we need to find the rule, or the
formula, or the method that has been used
in assigning the values to the class label
“Result”.
The problem of finding this rule or formula or
the method is the classification problem.
 Example 2 of Classification
Can we define breast cancer as malignant or benign based on tumour size
A tumor can be benign (not dangerous to health) or malignant (has the potential to be dangerous)

This is an example of a classification problem

● Classify data into one of two discrete classes - either malignant or not
● In classification problems, can have a discrete number of possible values for the
output

*e.g. maybe have four values

■ 0 - benign
■ 1 - type 1
■ 2 - type 2
■ 3 - type 4
Used only one attribute (size)
 Example 3 of Classification
● In other problems may have multiple attributes for same problem
definition of breast cancer
● We may also, for example, know age and tumor size
● Based on that data, you can try and define separate classes by
a. Drawing a straight line between the two groups
b. Using a more complex function to define the two groups (which we'll discuss later)
c. Then, when you have an individual with a specific
tumor size and who is a specific age,
you can hopefully use that information to place
them into one of your classes

● You might have many features to consider

a. Clump thickness
b. Uniformity of cell size
c. Uniformity of cell shape
Classification: Few Real life examples
Optical character recognition: problem of recognizing character codes from their
images, multiple classes.
Face recognition :the input is an image, the classes are people to be recognized,
multiple classes.
Speech recognition: the input is acoustic and the classes are words that can be
uttered
Medical diagnosis : the inputs are the relevant information about the patient and
the classes are the illnesses.
Classification Algorithms
a) Logistic regression

b) Naive Bayes algorithm

c) k-NN algorithm

d) Decision tree algorithm

e) Support vector machine algorithm

f) Random forest algorithm

Regression
In machine learning, a regression problem is the problem of predicting the value of
a numeric variable based on observed values of the variable. The value of the
output variable may be a number, such as an integer or a floating point value.
These are often quantities, such as amounts and sizes. The input variables may
be discrete or real-valued.
Regression : Example 1

Consider the data on car prices given in Table

Suppose we are required to estimate the price

of a car aged 25 years with distance 53240 KM
and weight 1200 pounds.

This is an example of a regression problem

because we have to predict the value of the
numeric variable “Price”.
 Example 2 of Regression
○ How do we predict housing prices
■ Collect data regarding housing prices and how they relate to size in feet

● Example problem: "Given this data, a friend has a house 750 square feet - how much can
they be expected to get?"

● What approaches can we use to solve this?

○ Straight line through data
■ Maybe $150 000
○ Second order polynomial
■ Maybe $200 000
○ One thing we discuss later - how to chose
straight or curved line?
○ Each of these approaches represent
a way of doing supervised learning
Example 2 of Regression continued….
● What does this mean?
○ We gave the algorithm a data set where a "right answer" was provided
○ So we know actual prices for houses
■ The idea is we can learn what makes the price a certain value from the
training data
■ The algorithm should then produce more right answers based on new
training data where we don't know the price already
1. i.e. predict the price
● We also call this a regression problem
○ Predict continuous valued output (price)
○ No discrete values
 Ensemble methods
● Ensemble methods are machine learning techniques that combine several base
models in order to produce one optimal predictive model.
● The ensemble methods in machine learning combine the insights obtained from
multiple learning models to facilitate accurate and improved decisions.
● In learning models, noise, variance, and bias are the major sources of error. The
ensemble methods in machine learning help minimize these error-causing factors,
thereby ensuring the accuracy and stability of machine learning (ML) algorithms.

Example 1: If you are planning to buy an air-conditioner, would you enter a showroom and
buy the air-conditioner that the salesperson shows you? The answer is probably no. In this
day and age, you are likely to ask your friends, family, and colleagues for an opinion, do
research on various portals about different models, and visit a few review sites before
making a purchase decision. In a nutshell, you would not come to a conclusion. Instead,
you would try to make a more informed decision after considering diverse opinions and
reviews. In the case of ensemble learning, the same principle applies.
Ensemble methods
Need of ensemble methods:
Machine learning models suffer from bias and/or variance.
● Bias is the difference between the predicted value and the actua lvalue by the model.
● (1) Bias is introduced when the model doesn’t consider the variation of data and
creates a simple model. The simple model doesn’t follow the patterns of data, and
hence the model gives errors in predicting training as well as testing data i.e. the
model with high bias and high variance.
● (2) When the model follows even random quirks of data, as patterns of data, then the
model might do very well on the training dataset, i.e. it gives low bias, but it fails on
test data and gives high variance.
● Therefore, to improve the accuracy (estimate) of the model, ensemble learning
methods are developed.
● Ensemble is a machine learning concept, in which several models are trained
using machine learning algorithms.
● It combines low performing classifiers (also called weak learners or base learners)
and combine individual model predictions for the final prediction.
Ensemble methods
● On the basis of the type of base learners, ensemble methods can be categorized
as homogeneous and heterogeneous ensemble methods.
● If the base learners are the same, then it is a homogeneous ensemble method.
● If base learners are different, then it is a heterogeneous ensemble method.
Types of Ensemble Methods

Ensemble techniques are classified into three types:

1. Bagging
2. Boosting
3. Stacking

Bagging is a way to decrease the variance in the prediction by generating additional data
for training from the dataset using combinations with repetitions to produce multiple sets
of the original data.

Boosting is an iterative technique that adjusts the weight of an observation based on the
last classification. If an observation was classified incorrectly, it tries to increase the weight
of this observation. Boosting, in general, builds strong predictive models.
1. Bagging, or Bootstrap Aggregating

● Bagging, also known as bootstrap aggregation, is the ensemble

learning method that is commonly used to reduce variance within a
noisy data set.
● BAGGing gets its name because it combines Bootstrapping and
Aggregation to form one ensemble model.
● In 1996, Leo Breiman introduced the bagging algorithm.
 1. Bagging, or Bootstrap Aggregating

Concept:

● Consider a scenario where we are looking at the users’ ratings for a product.
Instead of approving one user’s good/bad rating, we consider the average rating
given to the product.
● With an average rating, we can be considerably sure of the quality of the product.
Bagging makes use of this principle.
● Instead of depending on one model, it runs the data through multiple models in
parallel, and averages them out as the model's final output.
● Bagging is an acronym for Bootstrapped Aggregation.
● Bootstrapping means a random selection of records with replacements from the
training dataset.
 1. Bagging, or Bootstrap Aggregating
It has three steps:

1. Bootstrapping: Bagging leverages a bootstrapping sampling technique to create diverse

samples. This resampling method generates different subsets of the training data set. It
does so by selecting data points at random and with replacement. This means that
each time you select a data point from the training data set, you are able to select the
same instance multiple times. As a result, a value or instance repeated twice (or more) in
a sample.
2. Parallel training: These bootstrap samples are then trained independently and in
parallel with each other using weak or base learners.
3. Aggregation: Finally, depending on the task (that is, regression or classification), an
average or a majority of the predictions are taken to compute a more accurate
estimate. In the case of regression, an average is taken of all the outputs predicted by
the individual classifiers; this is known as soft voting. For classification problems, the
class with the highest majority of votes is accepted; this is known as hard voting or
majority voting.
 1. Bagging, or Bootstrap Aggregating
● ‘Random selection with replacement’ can be explained as follows:

1. Consider that there are 8 samples in the training

dataset. Out of these 8 samples, every weak learner
gets 5 samples as training data for the model. These 5
samples need not be unique, or non-repetitive.
2. The model (weak learner) is allowed to get a sample
multiple times. For example, as shown in the figure,
Rec5 is selected 2 times by the model. Therefore,
weak learner1 gets Rec2, Rec5, Rec8, Rec5, Rec4 as
training data.
3. All the samples are available for selection to next weak
learners. Thus all 8 samples will be available for next
weak learner and any sample can be selected multiple
times by next weak learners.
1. Bagging, or Bootstrap Aggregating

Bagging is a parallel method, which means several weak learners learn the data
pattern independently and simultaneously.
1. BAGGing, or Bootstrap AGGregating

Given a dataset, bootstrapped

subsamples are pulled.

A tree is formed on each

bootstrapped sample.

The results of each tree are

aggregated to yield the
strongest, most accurate
predictor.
1. BAGGing, or Bootstrap AGGregating

Advantages:

● Reduces over-fitting of the model.

● Handles higher dimensionality data very well.
● Maintains accuracy for missing data.
Disadvantages:

● Since the final prediction is based on the mean predictions from subset
trees, it won’t give precise values for the classification and regression models
2. Boosting
We saw that in bagging, every model is given equal preference, but if one model
predicts data more correctly than the other, then higher weightage should be given to
this model over the other.

Also, the model should attempt to reduce bias.

Boosting is used to create a collection of predictors. In this technique, learners are

learned sequentially with early learners fitting simple models to the data and then
analysing data for errors. Consecutive trees (random sample) are fit and at every step,
the goal is to improve the accuracy from the prior tree. When an input is misclassified
by a hypothesis, its weight is increased so that next hypothesis is more likely to classify
it correctly. This process converts weak learners into better performing model.

These concepts are applied in the second ensemble method that we are going to learn,
that is Boosting.
Boosting

Concept:

1. To start with, boosting assigns equal weights to all data points as all points are equally
important in the beginning. For example, if a training dataset has N samples, it assigns
weight = 1/N to each sample.
2. The weak learner classifies the data. The weak classifier classifies some samples
correctly, while making mistake in classifying others.
3. After classification, sample weights are changed. Weight of correctly classified sample
is reduced, and weight of incorrectly classified sample is increased. Then the next weak
classifier is run.
4. This process continues until model as a whole gives strong predictions.

Note: Adaboost is the ensemble learning method used in binary classification only.
Boosting

Boosting Steps:

● Draw a random subset of training samples d1 without replacement from the training set
D to train a weak learner C1
● Draw second random training subset d2 without replacement from the training set and
add 50 percent of the samples that were previously falsely classified/misclassified to train
a weak learner C2
● Find the training samples d3 in the training set D on which C1 and C2 disagree to train
a third weak learner C3
● Combine all the weak learners via majority voting.
Boosting

Advantages:

● Supports different loss function (we have used ‘binary:logistic’ for this example).
● Works well with interactions.
Disadvantages:

● Prone to over-fitting.
● Requires careful tuning of different hyper-parameters.
Ensemble Learning

Benefits of Ensemble Learning

● Improves accuracy
● Reduces variance (avoids overfitting)
● Enhances robustness
● Works well with high-dimensional and noisy data