Please enable JavaScript.
Coggle requires JavaScript to display documents.
Goal-based agents - pathfinding - Coggle Diagram
Goal-based agents - pathfinding
Problem Solving with Goals
FSMs require initial state, limiting for some agents.
Goals: Organize behavior by:
Limiting objectives.
Focusing actions considered by the agent.
Goal Formulation: First step based on current situation and performance measure.
Search: When environment is observable, discrete, known; solution is a fixed action sequence.
Well-Defined Problem
Initial State: (in(London))
Actions: Possible actions for each state (Actions(s) = {go(Norwich), go(Cardiff), go(Manchester)})
Transition Model: Result of an action in a state (Result(in(London), go(Norwich)) = in(Norwich))
State Space: Network or graph representing states and transitions (paths).
Goal Test: Condition to check if the goal state is reached ("Am I in Edinburgh yet?").
Path Cost Function: Evaluates the cost of a path (time, distance).
State Space Representation
Graph
Network: Symbolic representation of relationships.
Nodes: States.
Edges: Transitions between states.
Examples:
Tile-based games
Topography
Website index
Circuits
Protein interactions
Digraph: Directed edges with potentially different costs (one-way streets).
Types of Graphs/Networks
Undirected: Edges have no direction.
Directed: Edges have a specific direction.
Weighted: Edges have associated costs.
Search Algorithms
Depth-First Search (DFS):
Explores a path as far as possible before backtracking.
Guarantees visiting all nodes and edges in a connected graph.
Breadth-First Search (BFS):
Explores all neighbors of a node before moving to the next level.
Guarantees the shortest path to the target in unweighted graphs.
Best-First Search:
Uses a heuristic function to estimate the cost to reach the goal.
A Search:
*Combines cost of reaching a node and heuristic estimate to reach the goal.
Often more efficient than BFS or Best-First Search.
Example Problem:
Traveling Salesman Problem
Find the shortest route to visit all cities and return to the origin.
Real-world applications in routing and optimization.
Computationally challenging (NP-hard).