Please enable JavaScript.
Coggle requires JavaScript to display documents.
Goal-Based Agents & Search Techniques, image, image, image - Coggle…
Goal-Based Agents & Search Techniques
Goal-Based Agents
Definition:
Agents that decide what to do by formulating a goal and planning how to achieve it.
Goal formulation depends on
Current state: The agent’s current situation.
Performance measure: How success is judged (e.g., shortest path, lowest cost).
To solve problems, agents define
Initial State: Where the agent starts.
Goal Test: How to check if the goal is achieved.
Actions (Operators): All possible moves the agent can take.
Transition Model: Describes the result of an action.
Path Cost: Total cost of actions taken (e.g., time, distance).
State Space
Represents all possible configurations the agent can be in
States = Nodes
Actions = Edges connecting states
Path = Sequence of actions from start to goal
It's like a graph the agent explores to find solutions.
Search Algorithm Metrics
Completeness: Does the algorithm guarantee finding a solution if one exists?
Optimality: Will the algorithm find the best possible solution?
Time Complexity: How much time (or number of steps/nodes) does the algorithm take to find a solution?
Space Complexity: How much memory is required to run the algorithm?
Total Path Cost: What is the sum of all costs for actions in the final solution path?
Heuristics
A heuristic function (h(n)) estimates how close a state is to the goal.
For A* to be optimal
Admissible: h(n) ≤ true cost.
Non-negative: h(n) ≥ 0.
Used to improve search efficiency.
Genetic Algorithms
Genetic Algorithms are search and optimization techniques based on the principles of natural selection and genetics.
Core Concepts & Steps
Selection: Choose the fittest individuals (solutions) from the current population.
Crossover: Create new offspring by combining parts of two parents.
Mutation: Introduce random small changes in the offspring.
New Generation: Replace the old population with the new one (or partially replace it).
Solution Representation
Binary Strings: Common for simple problems (e.g., 101101)
Real Numbers: Used in mathematical or engineering problems
Other forms: Trees (for programs), permutations (for scheduling), etc.
Search Techniques
Search algorithms help agents explore the state space to find a path to the goal.
There are Two broad categories
Uninformed Search (Blind Search)
Depth-First Search (DFS)
How it works
Explores as far as possible down one branch before backtracking.
Uses a stack (LIFO) to track exploration.
Properties
Not complete: May go into infinite loops in cyclic or deep trees.
Not optimal: Might return a longer or costlier path.
Space-efficient: Only needs to store a single path at a time.
Best for: Problems where solutions are deep in the tree or memory is limited.
Breadth-First Search (BFS)
How it works
Uses a queue (FIFO) to keep track of what to explore next.
Explores nodes level-by-level starting from the root.
Properties
Optimal: Will find the shortest path if all step costs are equal.
Complete: Will find a solution if one exists.
Time/Space Complexity: O(b^d), where
d = depth of the shallowest solution
b = branching factor (number of successors per state)
Drawback: Uses a lot of memory as it stores all nodes at each level.
Informed Search (Heuristic Search)
Greedy Best-First Search
How it works:
Ignores the cost to reach that node (g(n)), only focuses on goal proximity.
Selects the node with the lowest h(n) — the closest estimate to the goal.
Properties:
Not optimal: May find a suboptimal (longer or costlier) path.
Fast: Often finds a path quickly.
Not complete: Might get stuck in loops or dead ends.
Best for: Speed is more important than accuracy.
A* Search
How it works
f(n) = g(n) + h(n) — total estimated cost of the path through that node.
Combines the cost to reach a node (g(n)) and the estimated cost to reach the goal (h(n)).
Properties
High memory usage: Keeps all explored paths in memory.
Optimal: If h(n) is admissible (i.e., never overestimates the true cost).
Complete: Always finds a solution if one exists.
Best for: Very powerful and widely used when optimality is required.
Search Techniques in Artificial Intelligence (AI)
Search techniques are used in AI to systematically explore a problem’s state space in order to find a solution.
Used in
Route Planning: Find the shortest or fastest path between two locations.
Robot Navigation: Robots must plan how to move from a starting point to a destination, avoiding obstacles.
Puzzle Solving: AI explores different configurations of a puzzle to reach the goal.
Example Problems
Route Finding Problem (Colombo to Kandy)
Components
States (S): Possible locations {Colombo, Rathnapura, Mathara, Kandy, Anuradhapura}
Initial State: Colombo
Actions: Move from one city to another
Goal: Reach Kandy
Solution Example: Colombo → Kegalle → Mawanella → Kandy
AI Perspective
This is a graph traversal problem.
Useful in GPS navigation, robotics, and logistics.
Can be solved with BFS, DFS, A* depending on whether the focus is on speed, memory, or optimality.
Wolf, Goat, and Cabbage Problem
Components
Initial State: Farmer, wolf, goat, and cabbage are all on the North side of the river.
Goal: Move them all safely to the South side.
Valid Actions (Operators)
Farmer goes alone
Farmer takes Goat
Farmer takes Wolf
Farmer takes Cabbage
Constraints
Farmer must always be present to supervise.
Cannot leave wolf with goat (wolf eats it)
Cannot leave goat with cabbage (goat eats it)
Solution Sequence
Farmer takes goat to South
Farmer returns alone to North
Takes cabbage to South
Brings goat back to North
Takes wolf to South
Returns alone to North
Takes goat to South again
AI Perspective
This is a constraint satisfaction problem.
Each move must satisfy rules (constraints).
Solved through state space search, checking valid and safe states.
Well-Defined Problem
A problem is said to be well-defined when all necessary components are clearly specified. This allows an AI agent to understand what actions are possible, what the goal is, and how to evaluate success or cost.
Steps
Initial State: The starting point of the problem.
Possible Actions: A set of available moves or operations the agent can take from any state.
Transition Model: Describes the result of taking an action in a given state.
Goal Test: A condition to check whether the goal has been reached.
Path Cost Function: Measures the cost of reaching the goal through a path.
Important Parameters in Search Algorithms
b = Branching Factor
Represents the average number of children (successor states) per node.
d = Depth of Shallowest Goal Node
The minimum number of steps from the root to the nearest goal.
m = Maximum Path Length
The maximum depth that the search algorithm might explore (especially in DFS).
