Transcript Artificial Intelligence

Artificial Intelligence
Search: 1
Ian Gent
[email protected]
Artificial Intelligence
Search: 1
Part I :
Part II:
Part III:
What is Search?
Presenting search abstractly
Basic search algorithms
What is AI?
 Very hard to define Artificial Intelligence
 not attempt at building machine to pass Turing Test
 Perhaps, exploiting power of machines to do tasks
normally considered intelligence?
 Practical day to day answer is:
 AI is what we don’t know how to do yet
 Once we know how to do something, it’s not AI
 e.g. optical character recognition, speech recognition
 Many AI problems involve combinatorial search
3
Example Search Problem: SAT
 We need to define problems and solutions
 Propositional Satisfiability (SAT)
 really a logical problem -- I’ll present as a letters game
 Problem is a list of words
 contains upper and lower case letters (order unimportant)
 e.g. ABC, ABc, AbC, Abc, aBC, abC, abc
 Solution is choice of upper/lower case letter
 one choice per letter
 each word to contain at least one of our choices
 e.g. AbC is unique solution to above problem.
4
Why is SAT a search problem?
 There is no efficient algorithm known for SAT
 all complete algorithms are exponential time
 3-SAT is NP-Complete
 3-SAT = each word contains exactly 3 letters
 NP-Complete
 we can recognise solutions in polynomial time
 easy to check letter choice satisfies each word
 all other NP problems can be solved by translation to SAT
 Many AI problems fall into NP-Complete class
5
Example: Travelling Salesperson
 Problem: graph with an cost for each edge
2
 e.g.
4
4
3
2
1
2
4
5
 Solution: tour visiting all nodes returning to base
 meeting some cost limit (or reaching minimum cost)
 e.g. minimum cost is 21 above
 TSP is NP-Complete
 easy to check that tour costs no more than limit
6
 (finding optimal cost in technically different complexity class)
Example (Not): Sorting
 Problem, a list of numbers
 e.g. 5 6 3 2 4 8
 Solution, list in ascending order
 e.g. 2 3 4 5 6 8
 In NP (easy to check that result in ascending order)
 Not NP-complete
 cannot solve SAT via sorting
 can be solved in O(n log n) time
 We know how to do it efficiently, so it’s not AI
7
Final Example: Games
 Problem: a position in a Chess/Go/… game
 Solution: a strategy to guarantee winning game
 Harder than NP problems
 it is not easy to check that a strategy wins
 can solve SAT via games
 Technically, games usually PSPACE-complete
 All NP-complete problems in PSPACE
 Games are valid AI application
 AI usually attacks NP-complete or harder search
problems
8
Presenting Search Abstractly
 Helps to understand the abstract nature of search
 search states, search spaces, search trees…
 know what particular search algorithms are trying to do
 There are two kinds of search algorithm
 Complete
 guaranteed to find solution or prove there is none
 Incomplete
 may not find a solution even when it exists
 often more efficient (or there would be no point)
 e.g. Genetic Algorithms
 For now concerned with complete algorithms
9
Search States
 Search states summarises the state of search
 A solution tells us everything we need to know
 e.g. in SAT, whether each letter is UPPER or lower case
 in TSP, route taken round nodes of graph
 This is a (special) example of a search state
 it contains complete information
 it solves the problem
 In general a search state may not do either of those
 it may not specify everything about a possible solution
 it may not solve the problem or extend to a solution
10
Search States
 Search states summarise the state of search
 E.g. in SAT
 a search state might be represented by aB
 E.g. in TSP
 a search state might specify some of the order of visits
 E.g. in Chess
 a search state might be represented by the board position
 (quiz for chessplayers: …and what else?)
11
Generalising Search
 With search states we can generalise search
 not just finding a solution to a problem
 Generally, find a solution which extends search state
 e.g. find solution to ABC, ABc, AbC, Abc, aBC, abC, abc
which extends aB
 there is no such solution though whole problem solvable
 Original search problem is to extend null state
 Search in AI by structured exploration of search
states
12
Search Space and Search Trees
 Search space is logical space composed of
 nodes are search states
 links are all legal connections between search states
 e.g. in chess, no link between states where W castles
having previously moved K.
 always just an abstraction
 think of search algorithms trying to navigate this extremely
complex space
13
Search Trees
 Search trees do not summarise
all possible searches
 instead an abstraction of one
possible search
 Root is null state
 edges represent one choice
ABC, ABc, AbC, Abc, aBC, abC, abc
state = ()
Choose A
a
(a)
Choose B
A
(A)
Choose C
 e.g. to set value of A first
 child nodes represent extensions
 children give all possible choices
 leaf nodes are solutions/failures
 Example in SAT
 algorithm detects failure early
 need not pick same variables
everywhere
B
(a B)
Impossible
b
(a b)
Impossible
C
(AC)
Choose B
B
(ABC)
Impossible
c
Ac
impossible
b
(AbC)
Solution
14
Why are search trees
abstract?
 Search trees are very useful concept
 but as an abstraction
 Search algorithms do not store whole search trees
 that would need exponential space
 we can discard nodes in search tree already explored
 Search algorithms store frontier of search
 I.e. nodes in search tree with some unexplored children
 Very many search algorithms understandable in
terms of search trees
 and specifically how they explore the frontier
15
Some classic search algorithms
 Depth-first search
 I.e. explore all nodes in subtree of current node before any
other nodes
 pick leftmost and deepest element of frontier
 Breadth-first search
 explore all nodes at one height in tree before any other
nodes
 pick shallowest and leftmost element of frontier
 Best-first search
 pick whichever element of frontier seems most promising
16
More classic search algorithms
 Depth-bounded depth first search
 like depth first but set limit on depth of search in tree
 Iterative Deepening search
 use depth-bounded search but iteratively increase limit
17
Next week on Search in AI
 Presentation of search algorithms in terms of lists
 e.g. depth-first = stack, breadth-first = queue
 Heuristics in search
 how to pick which variable to set
18