Please enable JavaScript.
Coggle requires JavaScript to display documents.
Goal-based agents - pathfinding - Coggle Diagram
Goal-based agents - pathfinding
Problem Solving steps
Goal formulation: - How to identify the goal according to the enviroment
Search:- Looks for sequence of actions to reach goal
State Space
A State space is the set of all states reachable from the initial state
Ex: Initial State: Negombo Goal: Colombo State space: Negombo, Katunayake, Ja Ela, Wattala
Well define problem
Intial State:- Starting point(ex: in Negombo)
Set of possible actions:- Actions to achieve the goal. (Ex: Goal is colombo, Actions ={go(Katunayake), go(Ja Ela), go(Wattala), go(Colombo)})
Transition model:- What each action does (Ex: Result(in (Negombo), go (Katunayake)) = in (Katunayake))
Digraph
this contains directed edges which means each edge has an orientation. typically, these edges can't go backwards
Nodes specifying a directed edge - ordered pair
Introduction
it operated based on a goal in front of it and makes decisions based on how best to reach that goal.
Goals help organize behavior
nodes and Edges
Nodes = State, Transition = Edge
Set of nodes linking set of edges
Weighted Edges
it costs time, distance, effort, money to transition
Types of searches
DFS- Depth First Search
This uses the idea of backtracking
This search of all nodes by going ahead, when if backwards on the same path.
BFS - Breadth First Search
Search each node from initial state.
since this is a graph data structure, BFS contains cycle. therefore, same node can be explored again
A* Search
A* an improvement because this introduces a heuristic into a regular graph-searching algorithm
Cost of each node = cost of edge + cost of previous node + estimated cost of reach target