CompSci 367 notes


Complete? Time Space Optimal f(n) Notes..
BFS Y (if b finite) Exponential Exponential Y (if step costs = 1) Uses a tonne of space (Graph search)
DFS N (loops/infinite m) Exponential Linear (only keeps best in mem) N
ID DFS Y Exponential Linear (discard after each step) Y (if step costs = 1) DFS + BFS advantages
Greedy N Exponential Exponential N h(n) Doesn’t care about g(n)
A* Y Exponential Exponential Y (if h is admissible + consistent) g(n) + h(n)
IDA* Y Exponential Linear Y g(n) + h(n) Iterates on the f-limit - start with h(init)
Weighted A* Y Exponential Exponential Y g(n) + h(n) * w will be no worse than w times as costly as optimal
Bidirectional A* Front-to-Back Y Exponential Exponentially smaller (b^(d/2)) Y g(n) + h(n) h(n) estimates diastase to the opposite terminal (init or goal), keeps searching for optimal
Bidirectional A* Front-to-Front Y Exponential Exponentially smaller (b^(d/2)) Y g(n) + h(n) h(n) estimates diastase to the opposite frontier, optimal on first collision!, cost of computing h grow exponentially
Min-Max Y Exponential Linear Y (against optimal opponent) minmax value
Min-Max a-b pruning Y Exponentially smaller (b^(m/2)) Linear .. minmax value doubles depth which can be done in the same time

Genetic algorithms

Constraint satisfaction problems (CSP)

Week 6 - 12

Decision making & choice

Reactive control for routine behaviour


Production systems

Causal models + Qualitative reasoning


Abductive reasoning

%% background knowledge
good_mood(X) :- did_well_on(X,Y).
did_well_on(X,Y) :- exam(Y), study(X,Y), take(X,Y).

%% suppose we observe
good_mood(john).    exam(e).    take(john,e).

%% suppose we want to explain why john is in a good mood
%% if we make one assumption:

%% we could derive good_mood(john) from this assumption and the observations
good_mood(john) :- /** observation to explain **/ 
    did_well_on(john,e) :- 
        study(john,e), /** assumption **/

Case-based and Analogical reasoning

Domain modelling and planning

Plan-Space planning

Graph planning

Machine Learning

Concept learning

Decision tree learning

Swarm Intelligence

Computational scientific discovery

Language + Dialogue

Cognition, Emotions, and Personality