Question? Leave a message!




Introduction to Artificial Intelligence

Introduction to Artificial Intelligence
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
Comment
Introduction to Artificial Intelligence Revision CS 3243 - Revision 1 Final Exam   Venue: TBA   Date: 23 November (Tuesday)   Time: 5:00 – 7:00 pm CS 3243 - Revision 2 Format   Open book   Six questions, emphasizing material covered after the midterm   Yes, all material in the course will be covered on the exam   Bring a (non-programmable) calculator with you CS 3243 - Revision 3 Outline   Agents   Search   Uninformed Search   Informed Search   Adversarial Search   Constraint Satisfaction   Knowledge-Based Agents   Uncertainty and Learning   Natural Language Processing CS 3243 - Revision 4 Agent types Four basic types in order of increasing generality:   Simple reflex agents   Model-based reflex agents   Goal-based agents   Utility-based agents CS 3243 - Revision 5 Simple reflex agents CS 3243 - Revision 6 Model-based reflex agents CS 3243 - Revision 7 Goal-based agents CS 3243 - Revision 8 Utility-based agents CS 3243 - Revision 9 Creating agents Where does the intelligence come from?   Coded by the designers Knowledge representation – predicate and first order logic   Learned by the machine Machine learning – expose naïve agent to examples to learn useful actions CS 3243 - Revision 10 Learning agents CS 3243 - Revision 11 Searching for solutions In most agent architectures, deciding what action to take involves considering alternatives   Searching is judged on optimality, completeness and complexity   Do I have a way of gauging how close I am to a goal?   No: Uninformed Search   Yes: Informed Search CS 3243 - Revision 12 Uninformed search   Formulate the problem, search and then execute actions   Apply Tree-Search   For environments that are   Deterministic   Fully observable   Static CS 3243 - Revision 13 Tree search algorithm   Basic idea:   offline, simulated exploration of state space by generating successors of already-explored states CS 3243 - Revision 14 Summary of algorithms   Breadth-First – FIFO order   Uniform-Cost – in order of cost   Depth-First – LIFO order   Depth-Limited – DFS to a maximum depth   Iterative Deepening – Iterative DLS   Bidirectional – also search from goal towards origin Criterion Breadth- Uniform Depth Depth Iterative Bidirection First Cost First Limited Deepening al Complete? Yes Yes No No Yes Yes d+1 ⎡C/e⎤ m l d d/2 Time O(b ) O(b ) O(b ) O(b ) O(b ) O(b ) d+1 ⎡C/e⎤ d/2 Space O(b ) O(b ) O(bm) O(bl) O(bd) O(b ) Optimal? Yes Yes No No Yes Yes CS 3243 - Revision 15 Repeated states: Graph-Search CS 3243 - Revision 16 Informed search estimated   Heuristic function h(n) = cost of the cheapest path from n to goal.   Greedy Best First Search   Minimizing estimated cost to goal   A Search   Minimizing total cost CS 3243 - Revision 17 Properties of heuristic functions   Admissible: never overestimates cost   Consistent: estimated cost from node n+1 is ≥ than cost from node n + step cost.   A using Tree-Search is optimal if the heuristic used is admissible.   Graph-Search needs a consistent heuristic. Why? CS 3243 - Revision 18 Local search   Good for solutions where the path to the solution doesn’t matter   Often work on a complete state   May not search systematically   Often require very little memory   Correlated to online search   Have only access to the local state CS 3243 - Revision 19 Local search algorithms   Hill climbing search – choose best successor   Beam search – take the best k successor   Simulated annealing – allow backward moves during beginning of search   Genetic algorithm – breed k successors using crossover and mutation CS 3243 - Revision 20