Please enable JavaScript.
Coggle requires JavaScript to display documents.
Pathfinding & Search - Coggle Diagram
Pathfinding & Search
Looking for a sequence of actions that reaches the end goal
Search Process
Components
-
State Space
- all possible states the agent can be in
Initial State
- the starting point of the agent
Goal State
- the desired end state the agent is trying to reach
Graph Representation
The state space is represented as a graph
Nodes
- states or locations
Edges
- connections between states
Weights
- cost of moving between nodes
Defining Problem
Defining states and actions
Initial State
- where the agent starts
Goal State
- what the agent is trying to achieve
Actions
- possible moves the agent can make
Transition model
- describes what state results from an action
Path cost
- total cost of a sequence of actions (distance, time, effort)
Goal Formulation
Setting objectives
Search Strategies
Blind Search
- explores without using any estimate of distance to goal
Breadth-First Search (BFS)
- explores all nodes level by level and guarantees shortest path in unweighted graph
Depth-First Search (DFS)
- follows one path to its end before backtracking.
Dijkstra’s Algorithm
- Focuses on path cost
Heuristic Search
- uses an estimate of distance to the goal to guide the search
A* Search
- combines path cost so far and estimated cost to goal to find optimal path efficiently