Please enable JavaScript.
Coggle requires JavaScript to display documents.
Week Four: Pathfinding Algorithms (Uninformed Search(Blind). (Depth…
Week Four: Pathfinding Algorithms
Search Tree:
● Search tree
● Branch = action, node = state
● Is current state a goal?
● If not EXPAND state
● Essence of search is to select 1 option and save others for later
The Frontier:
● Parent node
● Child node
● Leaf node
● Set of leaf nodes = frontier
(also known as open list)
Infrastructure of Search Algorithms.
Require data structure to keep of search tree = queue = lookup table.
For each node:
○ Node State (where am I)
○ Node Parent (where did I come from)
○ Node Action (where can I go)
○ Node Path Cost (total to get here)
Informed Search (Uses Heuristic).
Dijktra's Algorithms:
"The question of whether computers can think is like the question of whether submarines can swim."
● Shortest path in weighted graphs
● Builds on BFS by adding edge weights and adjusting BPSF (Best Path So Far)
● Edge relaxation (elastic)
Dijkstra's Algorithm 1:
● Find shortest path from A to F
● Create list of nodes to examine: { A(0) }
● Take node with lowest cost and visit all its neighbours.
Dijkstra's Algorithm 2:
● Cost of node = cost of edge + cost of previous node
● Note the parent (A)
● New list: { B(2), D(3), C(4) }
Dijkstra's Algorithm 3:
● Checking path B
● Path to D is redundant
● New list: { E(4), D(3), C(4) }
Dijkstra's Algorithm 4:
● Checking path D
● Finds better route to E
● New list: { E(3), C(4) }
Dijkstra's Algorithm 5:
Checking path E
● Finds F at cost 10
● List: { C(4), F(10) }
● Finally check path C
● And backtrack the shortest route (9) by using the parents
Best First Search:
● Node expanded based on evaluation function f(n) ● This function determines the search strategy
● Includes heuristic h(n)
● Heuristic = estimated cost of cheapest path from state at node n to goal
Greedy Best First Search:
● Expands the node closest to goal
● Using only the heuristic
● f(n) = h(n)
● Doesn’t go back to explore the others, so it’s quick, but...
A* is an improvement:
Cost of each node = cost of edge + cost of previous nodes + estimated cost to reach target.
● f(n) = g(n) + h(n)
● Where g(n) is path cost from start to n And h(n) is estimated cost from n to goal
● It’s optimal and complete!
● Just like Uniform Cost but g+h, not just g.
● Take into account an estimate of cost to target
● Heuristic: eg. distance as the crow flies
● Underestimate guarantees optimal path
● Stops you heading in wrong direction
Warnings:
● Algorithms that forget their history are doomed to repeat it!
● Loopy paths = infinite searches
● Maintain an explored set (closed list)
● Frontier separates explored and unexplored regions.
Uninformed Search(Blind).
Depth Limited:
○ Has a predetermined limit (no infinity)
○ What is the diameter of the problem?
Bidirectional
Depth First:
○ LIFO
○ Backtracking search uses less memory
Breath First:
○ FIFO - first in first out of the queue
○ Memory bigger problem than execution time
Uniform Cost:
○ Expands node with lowest path cost
○ Changes order of QUEUE
Iterative deepening depth first:
○ This limit gradually increases
Measuring Performance: How can we measure the performance of an algorithm?
Completeness - guarantee find solution .
Optimality - lowest path cost.
Time complexity - how long it takes .
Space complexity - how much memory required.
Web Links
http://www.redblobgames.com/pathfinding/grids/graphs.html
.
http://www.yaldex.com/games-programming/0672323699_ch12lev1sec7.ht
ml .
http://www.redblobgames.com/pathfinding/tower-defense/
.
https://www.scientificamerican.com/article/brainless-slimemolds/
.
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
http://heuristicswiki.wikispaces.com/IDA*
Genetic Algorithms:
● Measure fitness of each possibility
● Use this to determine probability of selection
● Randomly match 2 parents
● Swap match (like DNA) for offspring
● Random mutation
● Does it work? How? Chunks of usable code.
Slime Mould:
a simple organism that consists of an acellular mass of creeping jelly-like protoplasm containing nuclei, or a mass of amoeboid cells. When it reaches a certain size it forms a large number of spore cases.