Please enable JavaScript.
Coggle requires JavaScript to display documents.
Week Three: Goal-Based Agents - Pathfinding. (Problem Solving - Having…
Week Three: Goal-Based Agents - Pathfinding.
Problem Solving - Having GOALS.
SEARCH - Looks at the sequence of actions to reach goal.
If environment is observable, discrete, known solutions to problems is a fixed sequence of actions.
First Steps: GOAL FORMULATION - Based on current situation and performance measure.
Goals help organise behaviour by limiting objectives and the actions that agent needs to consider.
FSM requires an initial state - everything follows from that. Some agents have to sole problems.
Well-Defined Problem
Initial state - in(London).
Set of possible actions for state s, Actions(s) = { go(Norwich), go(Cardiff), go(Manchester)}.
Transition model - Results (s,a) - state that results from action a in state s. Result (in(London),goNorwich) = in(Norwich)).
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.
Weighted Edge: There may be a cost involved eg. time, distance, effort (Uphill).
Representation of Data:
Each node = integer.
Each edge connects two nodes.
Goal test (Am in Edinburgh yet?).
Path cost finding (eg How long.)
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
BFS (Breath First Search).
Do 1 step out in every possible direction, then step 2 e.t.c.
Skip edges that have already been explored.
Guarantees shortest path to target.
Explore each node radiating out from start.
A* is an improvement because it introduces a Heuristic.
Cost of each node =
cost of edge + cost of previous node + estimated cost to reach target.
DFS (Depth First Search).
Follow each nodes to its limit.
Reverse when at dead end.
Keep going when unexplored.
Develop deep into the graph space.
If graph is CONNECTED, guarantee that all nodes and edges are visited.
Graph - Network.
Website Index Circuit.
Graph is a symbolic presentation of a network.
Tile-based games(Grid) - Topology.
Human proteins (Dependencies).
Web Links
http://www.wired.com/2013/01/traveling-salesman-problem/all/
.
http://mathworld.wolfram.com/TravelingSalesmanProblem.html
.
http://qiao.github.io/PathFinding.js/visual/
.
Digraph
Where edges have different costs (eg. cannot go backwards, uphill vs downhill.)
Nodes specifying a directed edge - ordered pair.
With directed edges.