Problem Solving in Artificial Intelligence PDF

Problem solving Artificial intelligence Kristóf Karacs PPKE-ITK Program Problem solving by search Search including other agents Logic and inference Search in logic representation, planning Inference in case of constraints Bayesian n...

Problem solving Artificial intelligence Kristóf Karacs PPKE-ITK Program Problem solving by search Search including other agents Logic and inference Search in logic representation, planning Inference in case of constraints Bayesian networks Fuzzy logic Machine learning 1 Outline Concepts  State,state space, search tree, search path  Search strategy, solution Formalizing search Evaluation  Complexity, completeness, optimality, soundness Example Comparing strategies Search and AI Search methods are ubiquitous in AI systems An autonomous robot uses search  to decide which actions to take and which sensing operations to perform,  to quickly anticipate collision,  to plan trajectories,  to interpret large numerical datasets provided by sensors into compact symbolic representations,  to diagnose why something did not happen as expected,  etc... Many searches may occur concurrently and sequentially 2 Applications Route finding: airline travel, networks Package/mail distribution Pipe routing, VLSI routing Comparison and classification of protein folds Pharmaceutical drug design Design of protein-like molecules Games Automated Theorem Proving Machine learning Concepts in search State State space Search tree, search path Strategy Solution 3 Assumptions in basic search World is  static  discretizable  observable Actions are deterministic In many real world problems these assumptions do not hold Extended search techniques are required Steps of problem solving Goal formulation Problem formulation Search Solution Execution 4 Formal definition of search problems Initial state (s0S) Successor function: maps a state to a set of (action, successor state) pairs  s : S {A  S} Goal test: can be a set or a function Action costs Search strategy Decision function  State expansion  Choosing an action Non informed search Informed search 5 Search strategy The fringe is the set of all search nodes not yet expanded The fringe is implemented as a priority queue  insert(n,Q)  remove(Q) The ordering of the nodes in the queue defines the search strategy Revisiting states Most search strategies have two versions  States may be revisited  States may not be revisited Implementations  Flag for each state  Visited list Not appropriate for all strategies 6 Evaluation Time and space complexity Completeness  Statespace  Pruning Optimality Soundness  Search for nonexistent solutions  Incorrect search strategy Search strategies Breadth-first (BFS) Depth-first (DFS) 7 Search strategies Uniform-cost (UCS) Depth limited (DLS) Iterative deepening depth-first (IDS) Bidirectional (BS) Example a 2 2 G b c 2 8 1 5 d 2 f 3 e 9 5 9 1 s 4 h 1 4 r p 15 3 q 8 Example – 8 queens problem Place 8 queens on board  No one can “take” another 8-puzzle Initial state Goal state Formal definition of search problems Initial state (s0S) Successor function: maps a state to a set of (action, successor state) pairs  s : S {A  S} Goal test: can be a set or a function Action costs 9 Implementation Open http://users.itk.ppke.hu/~karacs/AI/lab/search Download search_demo_UI_1.html and search1.js to the same folder Open example.html in a browser, and open the Javascript console by pressing F12, or right-click anywhere, Inspection, Console tab  Alternatively you can use a node.js console as well Function stubs are included with some coding hints Open search1.js with an editor, and implement  BFS  DFS  Optional: add a visited list to both algorithms  Optional: iterative deepening DFS Count the iteration steps, define an upper bound for the steps and for the size of the queue / stack and the visited list as well Implementation States: arrays of numbers with fixed length (the length is given by the length of the initialState array) Goal: reach the state in which elements are sorted incrementally  Function goal(state) is already implemented, returns true or false State transition: Swap two elements in the array  Function stateTransitions(state) is implemented, returns an array of all states available from the state Auxiliary functions  isMember(state, list) returns true if state is already in list  shuffle(array) shuffles the instances in array randomly  log(message) prints message to the text area or to the console 10  Formal definition of search problems Initial state (s0S) Successor function: maps a state to a set of (action, successor state) pairs  s : S {A  S} Goal test: can be a set or a function Action costs Comparison of search strategies d: depth of shallowest solution b: branching factor m: maximum depth of search tree l: depth limit Measure BFS UCS DFS DLS IDS BS Time Space Optim. Compl. 11  Comparison of search strategies d: depth of shallowest solution b: branching factor m: maximum depth of search tree l: depth limit Measure BFS UCS DFS DLS IDS BS Time bd bd bm bl bd bd/2 Space bd bd bm bl bd bd/2 Optim. Y Y N N Y Y Compl. Y Y N Y, Y Y if l  d Summary Concepts  State,state space, search tree, search path  Search strategy, solution Formalizing search Evaluation  Complexity, completeness, optimality, soundness Comparison of strategies 12