Please enable JavaScript.
Coggle requires JavaScript to display documents.
Intro to AI 2 (Reasoning and Planning (Situations - Basically states,…
Intro to AI 2
Reasoning and Planning
Situations - Basically states, starting with S0. S1 = result(A, S0) where A is an action.
Fluents - Functions that may or may not be true in situations. Eg. Holding(A, S0) means that A is holding in S0.
-
-
-
-
Situation Calculus - Uses all 3 axioms to describe what has changed, what hasn't changed and all the actions that can be taken, of every state. Very inefficient since the same things will be wrote twice.
STRIPS - Eg. Move(b, x, y) - Preconditions: On(b,x) ^ Clear(b) ^ Clear(y) , Effects: On(b,y) ^ Clear(x) ^ ¬On(b,x) ^ ¬Clear(y)
-
-
Goal Regression - Works back from the goal state, to map what conditions need to be met to reach it.
Search
Space State Graph - Shows every possible outcome as nodes, and and the arcs represent all valid moves between the states.
Search Tree - A tree where the children of a node are the relationships between them. Nodes are not repeated in this as that would create loops. Each branch has a weight for calculating a total distance
Breadth First - Nodes are visited in levels so once a level has been iterated through, the next level is evaluated. Complete, Admissible, O(b^d) time, O(b^d) memory
-
-
Depth First - Branches are fully iterated before moving on to the next branch. Not complete (Graph could be infinite), inadmissible, O(bm) memory, O(b^m) time
Depth Limited - Depth but has a limit L for the furthest it will traverse. Complete if d<L, inadmissible, O(bL) memory, O(b^L) time
Depth First Iterative Deepening (DFID) - Same as depth limited, except it will do L = 1, then repeat will L = 2 etc. Complete and admissible, O(bd) memory and O(b^d) time
Open nodes are nodes that can be selected for expansion, in order, closed nodes have already been expanded.
Informed Search
Heuristics - Special rules that are designed to cut down the number of node expansions to find the goal node. Should be an underestimate at every single node for the algorithm to be admissible. Also known as greedy.
Hill climbing - Generate the children of the current state. Find the euclidean distance (pythag) to the goal node for each child and take the shortest. Can get stuck if the current node is closer. Also called greedy search. Complete but inadmissible.
A* - Calculates g(X) which is the total distance travelled so far, h(X) is euclidean distance, and f(x) = g(x) + h(x). Takes the shortest f(x) of any node. Algorithm doesn't terminate when the goal is found, it terminates when all f(x) > current best path. Admissible. Duplicate nodes need to be marked with subscript
Informedness - If one heuristic is more accurate than another, it is more informed.
Uniform cost search. Basically Dijkstra's, where it will generate all children and follow the shortest path each time (so doesn't use a heuristic). Complete and admissible.
-
Bidirectional Searches - When a search algorithm is used from both the current node and goal node simultaneously. Saves on time and memory.
Logic
Resolution - P v ¬P cancel out. You cant cancel out 2 things in 1 step. Technically its not complete (eg. {P, R} : PvR)
Conjunctive Normal Form (CNF) - clauses (eg. P v ¬Q), separated by ^
-
-
-
Resolution Refutation - Negate what you want to prove, convert to CNF and put in the braces. Then find a contradiction.
Game trees
In 2 player games (eg. Chess), these algorithms look a few steps ahead at each possible combination and calculates the best worse-case scenario and which move to make.
It assumes the other player is going to pick their best move which isn't always the case with human players.
The tree is iterated depth first, where at each empty node, the children of that node are evaluated based on min or max. Then the reverse is done 1 level up etc etc.
Alpha-Beta Pruning - If a node at a min branch has a value of 10 and the max from the branch below is 11, then the rest of the branch can be left, so it saves unnecessary evaluations.