Chapter 4 - Search in Complex Environments (part 1).pdf

Search in Complex Environments ARTIFICIAL INTELLIGENCE JUCHEOL MOON 1 𝑛-queens problem ▪Put 𝑛 queens on an 𝑛 × 𝑛 board with no two queens on the same row, column, or diagonal ▪How we can solve this?...

Search in Complex Environments ARTIFICIAL INTELLIGENCE JUCHEOL MOON 1 𝑛-queens problem ▪Put 𝑛 queens on an 𝑛 × 𝑛 board with no two queens on the same row, column, or diagonal ▪How we can solve this? 2 2 1  Iterative improvement algorithms ▪In many problems, path is irrelevant; ▪the goal state itself is the solution ▪In such cases, can use iterative improvement algorithms; ▪keep a single “current” state, try to improve it 3 3 Hill-climbing ▪Strategy; Move a queen to reduce number of conflicts ▪Cost function ℎ; is the number of pairs of queens that are attacking each other X X X X X X X X X X X X 4 4 2  Local search space ▪To solve 𝑛-queens problem ▪Move a queen to adjacent positions X X X X X X X X X X X X X X X X X X X X X X 5 5 Local search space ▪To solve 𝑛-queens problem ▪Move a queen to adjacent positions X X X X X X X X X X X X X X X X X X X X X X X X X 6 6 3  Local search space ▪Another strategy ▪Different local search space X X X X 7 7 Hill-climbing ▪Like climbing Everest in thick fog with amnesia 8 8 4  Hill-climbing ▪Goal ▪Finding a global maximum 9 9 Hill-climbing ▪Problems? 10 10 5  Hill-climbing ▪Problems ▪Local maxima ▪Shoulder ▪Plateau ▪Solutions ▪Random sideways moves ▪ escape from shoulders, but loop on flat maxima ▪Random-restart hill climbing ▪ overcomes local maxima ▪ trivially complete 11 11 Random-restart hill climbing ▪If at first you don’t succeed, try, try again. ▪If each hill-climbing search has a probability 𝑝 of success; then the probability that the 𝑘 𝑡ℎ trial (out of 𝑘 trials) is the first success is 𝑃𝑟 𝑋 = 𝑘 = ▪Expected number of restarts; ▪𝐸 𝑋 = 12 12 6  Hill-declining(?) ▪Goal ▪Finding a global minimum ▪Traditionally, we use the term ‘Hill-climbing’ even for finding a minimum 13 13 Simulated annealing ▪Escape local maxima by allowing some “bad” moves ▪Random-restart in limited space 14 14 7  Simulated annealing ▪Escape local maxima by allowing some “bad” moves ▪but gradually decrease their size and frequency Fluctuation 15 15 𝐾 parallel hill-climbing ▪Idea ▪Run 𝑘 independent hill-climbing searches ▪Can we improve this idea? 16 16 8  Local beam search ▪Idea ▪keep 𝑘 states instead of 1 ▪choose top 𝑘 of all their successors ▪Not the same as 𝑘 searches run in parallel ▪Searches that find good states recruit other searches to join them ▪Problem ▪quite often, all 𝑘 states end up on same local hill 17 17 9