Please enable JavaScript.
Coggle requires JavaScript to display documents.
Goal-based Agents and Pathfinding - Coggle Diagram
Goal-based Agents and Pathfinding
Problem-solving with Goals
Goals organize behavior by limiting objectives and actions
Goal Formulation: Based on current situation and performance measure
Solution: Fixed sequence of actions if the environment is observable, discrete, and known
Search: Looks for a sequence of actions to reach the goal
Well-defined Problem
Initial State: Example - in(London)
Set of Possible Actions: Example - {go(Norwich), go(Cardiff), go(Manchester)}
Transition Model: State resulting from an action, e.g., Result(in(London), go(Norwich)) = in(Norwich)
Goal Test: Example - am I in Edinburgh yet?
Path Cost Function: Example - how long?
State Space
Representation: Network or graph
State = Node, Transition = Edge
Nodes and Edges: G = {N, E}, each node is an integer, each edge connects two nodes
Weighted Edge: Cost involved (e.g., time, distance, effort)
Digraph: Directed edges with different costs
Examples of Contexts
Toy problem vs. Real-world problem
Graph as a Network: LinkedIn connections, tile-based game topography, website index, circuit, human proteins dependencies
Travelling Salesman Problem
Applications: Routing trucks, material handling in warehouses, overhauling gas-turbine engines, genome sequencing
Complexity: Increases exponentially with more destinations
Types of Searches
Get to the target
Visit every node (in what order?)
Find the best path to target
Best path using the least effort
Search Algorithms
DFS (Depth First Search): Follow each node to its limit, reverse at dead end, guarantee all nodes and edges visited if graph is connected
BFS (Breadth First Search): Explore each node radiating out from start, guarantee shortest path to target
Best First Path Search
A* Search: Improvement with heuristic, cost of each node = cost of edge + cost of previous node + estimated cost to reach target
Links
http://qiao.github.io/PathFinding.js/visual/
http://www.wired.com/2013/01/traveling-salesman-problem/all/