Please enable JavaScript.
Coggle requires JavaScript to display documents.
Goal-Based Agents - Pathfinding - Coggle Diagram
Goal-Based Agents - Pathfinding
Problem-Solving - Having GOALS
Goals help organize behaviour by limiting objectives and the actions that the agent needs to consider
First step: GOAL FORMULATION - Based on current situation and performance measure
FSM requires an initial state - everything follows from that. Some agents have to solve problems
If environment is observable, discrete, known solution to problem is a fixed sequence of actions
SEARCH - Looks for sequence of actions to reach goal
Well-defined problem
Initial state
Transition model - Result (s, a) - state that results from action a in state s
STATE SPACE:
Network or Graph path = sequence of states connected by sequence of actions
Historically from representing semantic networks
state = node Transition = edge
Nodes and Edges: {N, E} Set of nodes linking set of edges
Data Representation
Each node = integer.
Each edge connects two nodes
Weighted Edge
May be a cost involved eg. time, distance, effort (uphill)
Set of actions
Digraph
With directed edges
Edges have different costs (eg. can't go backwards, uphill vs downhill)
Nodes specifying a directed edge - ordered pair
Graph = Network
Tile-based game (grid) - Topography
Graph = symbolic representation of a network
Website Index Circuit
Human proteins (dependencies)
Types of searches
Get to the target
Visit every node (in what order?)
Find best path to target
Best path to target using least effort
DFS - Depth First Search
Follow each node to its limit
Reverse when dead end
Keep going if unexplored
Delve deep into the graph space
If graph is CONNECTED, guarantee that all nodes and edges are visited
BFS - Breadth First Search
Explore each node radiating out from start
Do 1 step out in every possible direction, then 2 steps etc.
Skip edges that have already been explored
Guarantees shortest path to target
A*
A* an improvement because it introduces a heuristic.
Cost of each node = cost of edge + cost of previous node + estimated cost to reach target
Web Links
http://www.kongregate.com/games/WhereIs_Treasure/city-traffic-simulator
http://www.wired.com/2013/01/traveling-salesman-problem/all/
http://mathworld.wolfram.com/TravelingSalesmanProblem.html
http://qiao.github.io/PathFinding.js/visual/