Please enable JavaScript.
Coggle requires JavaScript to display documents.
Goal-Based Agents and Search Techniques (3) - Coggle Diagram
Goal-Based Agents and Search Techniques (3)
Goal-Based Agents & Problem Solving by Search
Goal Formulation
First step in problem solving.
Formulate goals based on:
Current situation.
Performance measures.
If environment is
Observable, Discrete, Known → the solution will be a fixed sequence of actions.
Assume the problem has a set of states S
Goal
Solution
Set of operations
Path cost
initial state
Well-defined Problem
Goal Test:
Check if current state meets the goal (e.g., "Am I in Edinburgh?").
Transition Model is defined:
What happens after each action?
E.g., Result(in(London), go(Norwich)) = in(Norwich)
Possible Actions are given (e.g., {go(Norwich), go(Cardiff), go(Manchester)}).
Initial State is given (e.g., in(London)).
Path Cost Function:
Cost related to achieving the goal (e.g., time, distance).
State Space
Forms a Directed Graph
Edges = actions.
Path = sequence of nodes connected by actions.
Nodes = states
All states reachable from initial state by applying actions.
Simple Problems
Route Finding (Colombo to Kandy)
Actions: Moving between cities.
Goal: Arriving at Kandy.
Initial State: Colombo.
Solution Example:{Colombo → Kegalle → Mawanella → Kandy}
States (S): {Colombo, Rathnapura, Mathara, Kandy, Anuradhapura, ...}
Wolf, Goat, and Cabbage Problem
Goal: All safely on South side.
Initial State: Farmer, wolf, goat, cabbage at North side.
Operators (Actions):
Farmer can go alone
Farmer go with goat
Farmer go with wolf
Farmer go with cabbage
Constraints:
Cannot leave goat with cabbage.
Cannot leave wolf with goat.
Set of states
S0 – All on North side.
Sg – All on South side.
Several intermediate states (moving goat, wolf, cabbage).
Solution Sequence
Farmer takes goat to South.
Farmer returns alone to North.
Farmer takes cabbage to South.
Farmer brings goat back to North.
Farmer takes wolf to South.
Farmer returns alone to North.
Farmer takes goat to South again.
Measuring Search Algorithm Performance
Optimality
Time Complexity
Completeness
Space Complexity
Total Cost
Search Techniques in AI
General Idea: Search through a modelled state space to solve a problem.
Used in
Route planning.
Robot navigation.
Puzzle solving (8-Queens, Blocks World, etc).
Types of Search Strategies
Uninformed (Blind) Search
Only know if a state is a goal or not.
Examples:
Breadth-First Search (BFS).
Data structure: Queue (FIFO).
Properties:
Complete (if b is finite).
Optimal (if step cost = 1).
High time/space: O(b^d).
Expand shallowest nodes first (level-by-level).
Depth-First Search (DFS).
Expand deepest nodes first.
Data structure: Stack (LIFO).
Properties:
Not complete (in infinite spaces).
Not optimal.
Lower memory needs than BFS.
Faster if solutions are deep.
No information about the goal.
Informed (Heuristic) Search
Expands more promising nodes first.
Examples:
Greedy Search.
A* Search.
Uses heuristic (estimate cost to goal).
Important Parameters
d = depth of shallowest goal node.
m = maximum path length.
b = branching factor (children per node).
Informed Search
Greedy Search
Example: Straight-line distance to Bucharest.
Properties:
Not complete (loops).
Not optimal.
Fast if heuristic is good.
Choose node with lowest estimated cost to goal (h(n)).
A* Search
f(n) = g(n) + h(n).
g(n) = cost so far, h(n) = estimated remaining cost.
Properties:
Complete.
Optimal (if h(n) is admissible).
High space complexity (stores all nodes).
Heuristics
A heuristic function h(n) gives an estimate from node n to goal.
Requirements for A*:
h(n) ≤ true cost to reach goal (admissible).
h(n) ≥ 0.
Genetic Algorithm (GA)
Search-based optimization technique.
Inspired by natural evolution.
Steps in GA
Crossover: Combine selected individuals.
Mutation: Random small changes to introduce diversity.
Selection: Choose best individuals.
Next Generation: Form new population and repeat.
Representation in GA
Different ways of representing solutions (e.g., binary strings, real numbers).
Different methods for crossover and mutation based on the problem.