Probability Notations and AI Planning Methods

Basic Probability Notations and Examples

Probability is the branch of mathematics that deals with the likelihood of occurrence of an event. The probability of an event ranges from 0 to 1, where:

• 0 indicates an impossible event.
• 1 indicates a certain event.

Probability is widely used in Artificial Intelligence, Machine Learning, Statistics, Data Science, and Decision Making.

1. Sample Space (S)

The sample space is the set of all possible outcomes of an experiment.

Example: When a die is rolled, S = {1, 2, 3, 4, 5, 6}.

2. Event (A)

An event is a subset of the sample space.

Example: Event A = Getting an even number, so A = {2, 4, 6}.

3. Probability of an Event

The probability of an event is calculated as:

P(A) = (Number of favorable outcomes) / (Total number of outcomes)

Example: Probability of getting an even number on a die: P(A) = 3/6 = 1/2.

4. Complement of an Event

The complement of event A is denoted by A' or Aᶜ.

P(A′) = 1 − P(A)

Example: Probability of not getting an even number: P(A′) = 1 - 1/2 = 1/2.

5. Union of Two Events (A ∪ B)

The union represents the occurrence of A or B or both.

P(A ∪ B) = P(A) + P(B) − P(A ∩ B)

6. Intersection of Two Events (A ∩ B)

The intersection represents the occurrence of both A and B simultaneously.

Example:
A = Even numbers = {2, 4, 6}
B = Numbers greater than 3 = {4, 5, 6}
Then, A ∩ B = {4, 6}.

7. Conditional Probability

Conditional probability is the probability of event A occurring given that event B has already occurred.

P(A | B) = P(A ∩ B) / P(B)

Example: If a card drawn is known to be a face card, the probability that it is a King is: P(King | Face Card) = 4/12 = 1/3.

8. Independent Events

Two events are independent if the occurrence of one does not affect the occurrence of the other.

Formula: P(A ∩ B) = P(A) × P(B)

Example: Tossing a coin and rolling a die are independent events.

Comprehensive Example: Rolling a Die

Sample Space: S = {1, 2, 3, 4, 5, 6}

Let:
A = Even numbers = {2, 4, 6}
B = Numbers greater than 4 = {5, 6}

Then:
P(A) = 3/6 = 1/2
P(B) = 2/6 = 1/3
A ∩ B = {6}

Important Probability Rules

• 0 ≤ P(A) ≤ 1
• P(S) = 1
• P(∅) = 0
• P(A′) = 1 − P(A)
• P(A ∪ B) = P(A) + P(B) − P(A ∩ B)

Applications of Probability

• Artificial Intelligence
• Machine Learning
• Medical Diagnosis
• Weather Forecasting

Classical and Hierarchical Planning in AI

Planning is an important area of Artificial Intelligence (AI) that involves finding a sequence of actions to achieve a desired goal from an initial state. Planning enables intelligent agents and robots to make decisions and solve problems efficiently.

(i) Classical Planning

Definition: Classical Planning is an AI planning technique in which the environment is fully observable, deterministic, static, and known. The planner generates a sequence of actions that transforms the initial state into the goal state.

Characteristics of Classical Planning

• Environment is fully observable.
• Actions are deterministic (the same action always produces the same result).
• Only one agent performs the actions.
• The world does not change while planning.
• The initial state and goal state are completely known.

Components

1. Initial State: Starting condition.
2. Goal State: Desired final condition.
3. Actions (Operators): Operations used to reach the goal.
4. State Space: All possible states.

Example: Robot Navigation

Initial State: Robot is in Room A.
Goal: Robot should reach Room C.
Actions: Move(A, B), Move(B, C)
Plan: Room A → Room B → Room C

Advantages and Limitations

Advantages: Simple to implement, produces optimal plans in deterministic environments, and is efficient for structured environments.
Limitations: Cannot handle uncertainty, assumes complete knowledge, and is not suitable for dynamic environments.

(ii) Hierarchical Planning

Definition: Hierarchical Planning solves complex problems by breaking a high-level task into smaller subtasks. This is also known as Hierarchical Task Network (HTN) Planning. Instead of planning every action directly, it decomposes complex goals into simpler tasks until primitive actions are obtained.

Characteristics of Hierarchical Planning

• Uses task decomposition.
• Plans are organized in multiple levels.
• High-level goals are divided into smaller subtasks.
• Suitable for large and complex planning problems.

Components

• High-Level Task
• Subtasks
• Primitive Actions
• Methods (rules for decomposition)

Example: Travel Planning

High-Level Goal: Travel from Hyderabad to Delhi.
Task Decomposition:
Travel to Delhi
├── Book Flight
├── Pack Luggage
├── Go to Airport
├── Board Flight
└── Reach Delhi

Advantages and Limitations

Advantages: Handles complex problems efficiently, reduces planning complexity, and produces reusable plans similar to human problem-solving.
Limitations: Requires domain-specific knowledge, and creating task hierarchies can be difficult.

The GraphPlan Algorithm for Planning Graphs

Algorithm Steps

PlanningGraph(Initial_State, Goal_State)

1. Create the initial state level S₀ using the initial state.
2. Repeat until the goal is reached or the graph levels stop changing:
   • a. Generate an action level Aᵢ: Add all actions whose preconditions are satisfied in Sᵢ and add persistence (No-Op) actions.
   • b. Compute mutex (mutual exclusion) relations: Identify conflicting actions and inconsistent states.
   • c. Generate the next state level Sᵢ₊₁: Add all positive effects of actions in Aᵢ.
   • d. Compute mutex relations among states.
   • e. If Goal_State appears in Sᵢ₊₁ and the goal literals are not mutually exclusive, Extract the plan. Else, continue expanding.
3. If no new states or actions are added and the goal is not found, return "No Solution".
4. Return the extracted plan.

Step-by-Step Explanation

1. Create Initial State (S₀): Begin with all facts true in the initial state.
2. Generate Action Level (A₀): Include every action whose preconditions are satisfied, including No-Op actions.
3. Generate Next State (S₁): Apply all actions to obtain new facts.
4. Compute Mutex Relations: Identify actions or states that cannot occur simultaneously.
5. Check Goal: If all goal conditions appear without mutex conflicts, extract the solution plan.
6. Repeat: Continue expanding the graph until a solution is found or expansion stops.

Example Problem

Initial State: Robot at Room A, Door Open.
Goal: Robot at Room B.
Available Action: Move(A, B).

Planning Graph Structure:
State Level S0: [Robot at A, Door Open]
↓
Action Level A0: [Move(A, B)]
↓
State Level S1: [Robot at B, Door Open]

Since "Robot at B" is present in S₁, the goal is achieved. Plan: Move(A, B).

Advantages and Limitations

Advantages: Efficiently finds valid plans, uses mutex relations to reduce search space, and estimates shortest plan length.
Limitations: Graph size increases for large problems, requires significant memory, and is less suitable for uncertain environments.