Transcript ppt
Computer Science 1000 AI – A Brief Overview Artificial Intelligence definition: many! ``The exciting new effort to make computers think ... machines with minds, in the full and literal sense'' (Haugeland, 1985) ``The automation of activities that we associate with human thinking, activities such as decision-making, problem solving, learning ...'' (Bellman, 1978) ``The art of creating machines that perform functions that require intelligence when performed by people'' (Kurzweil, 1990) ``The study of how to make computers do things at which, at the moment, people are better'' (Rich and Knight, 1991) ``The study of mental faculties through the use of computational models'' (Charniak and McDermott, 1985) ``The study of the computations that make it possible to perceive, reason, and act'' (Winston, 1992) “Computational Intelligence is the study of the design of intelligent agents” (Poole et. al. 1998) “AI ... is concerned with intelligent behaviour in artifacts.” From Russel & Norvig. Artificial Intelligence: A Modern Approach Artificial Intelligence definition: many! ``The exciting new effort to make computers think ... machines with minds, in the full and literal sense'' (Haugeland, 1985) ``The study of mental faculties through the use of computational models'' (Charniak and McDermott, 1985) Systems that think like humans ``The automation of activities that we ``The study of the computations that make Systems that think rationally it possible to perceive, reason, and act'' (Winston, 1992) associate with human thinking, activities such as decision-making, problem solving, learning ...'' (Bellman, 1978) ``The art of creating machines that perform functions that require intelligence when performed by people'' (Kurzweil, 1990) Systems that act like humans ``The study of how to make computers do things at which, at the moment, people are better'' (Rich and Knight, 1991) “Computational Intelligence is the study of the design of intelligent agents” (Poole et. al. 1998) “AI ... is concerned with intelligent Systems that act rationally behaviour in artifacts.” From Russel & Norvig. Artificial Intelligence: A Modern Approach Acting Humanly – the Turing Test* Two identical rooms labeled A and B are connected electronically to a judge who can type questions directed to the occupant of either room. A human being occupies one room, and the other contains a computer. The judge's goal is to decide, based on the questions asked and the answers received, which room contains the computer. If after a reasonable period of time the judge cannot decide for certain, the computer can be said to be intelligent. The computer is intelligent if it acts enough like a human to deceive the judge. * Text Acting Human – Historical Attempts ELIZA programmed in 1966 programmed to ask questions in dialog like a psychotherapist and a patient Took word cues, noticed use of negatives Dialog was essentially pre-planned to appear intelligent, but was not http://www.masswerk.at/elizabot/eliza.html http://nlp-addiction.com/chatbot/eliza/ http://www.stanford.edu/group/SHR/42/text/dialogues.html#note10 Chatterbot ELIZA was an early example of a chatterbot A chatterbot (or chatbot) is a type of conversational agent designed to simulate an intelligent conversation with one or more human users via auditory or textual methods. Chatterbots – Examples PARRY (1972) JABBERWACKY (1997) one of the first internet chatterbots http://www.jabberwacky.com/ CLEVERBOT (1997) simulated a paranoid schizophrenic. http://www.cleverbot.com/ ALICE (2001) Artificial Linguistic Internet Computer Entity inspired by ELIZA http://www.alicebot.org/ Loebner Prize a competition in the spirit of the Turing Test held annually since 1990 initiated by Hugh Loebner prizes include: $100,000 + gold medal: the first computer whose responses were indistinguishable from a human's must convince 30% of judges never been won ~$3000 (varies) + bronze medal: computer program that outperforms all other programs Loebner Prize format in each round, a judge holds a conversation with a human and machine after the round is over, judge must decide which is which 5 minute rounds Loebner Prize notable achievements ALICE was the Loebner winner 3 times (2001, 2002, 2004) ELBOT (2008) convinced 3 of 12 judges that it was the human Turing Test Turing Test remains historically significant, and has driven some advances in field however, most AI research has not focused on simulating human intelligence “Aeronautical engineering texts do not define the goal of their field as making ‘machines that fly so exactly like pigeons that they can fool even other pigeons’” – Russel and Norvig Problem Solving rather than create a universally intelligent machine or program, AI research often focuses on a more specific task examples: pattern recognition robotics (next lecture!) natural language processing path finding Problem Solving the variety of problems to solve have produced a variety of different AI techniques examples: path finding – A* search, greedy search pattern recognition – neural networks searching – A*, genetic algorithms diagnosis – fuzzy logic, Bayesian networks, etc Path Finding find a path from start to destination domain can be: domain consists of a set of points a map (GPS) a virtual world in a game a series of networked computers etc ... one of those points is your start one (or more) of those points can be a destination each point is connected to zero or more other points Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Wood Mountain Path Finding the general objective is to find a path between start and destination for example, find a path between Val Marie and Kincaid Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Wood Mountain Path Finding there are many strategies for finding paths, but most follow a similar theme begin at your starting point consider all positions that are reachable from that point then consider all positions that are reachable from those points and so on, until you reach your destination, or run out of options you must store your current path different algorithms use different selection techniques for what to try “next” Path Finding Example: DFS (Depth-first search) begin at your starting point repeat while you have not reached your destination, or you have no other options choose a new point that you have not yet visited that is connected to you current point if such a point exists, traverse to it if not, then back up to your previous position Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Begin at starting position Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Choose a new point that you have not yet visited that is connected to you current point: Cadillac Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Choose a new point that you have not yet visited that is connected to you current point: Ponteix Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Choose a new point that you have not yet visited that is connected to you current point: Mankota Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Choose a new point that you have not yet visited that is connected to you current point: Wood Mountain Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie No points connected to WM that we have not yet visited. Must back up to Mankota. Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Choose a new point that you have not yet visited that is connected to you current point: Kincaid Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie We now have a path between Val Marie and Kincaid. Wood Mountain Path Finding DFS (Depth-first search) advantages: simple memory efficient (beyond scope of class) disadvantages: not guaranteed to find shortest path first (smallest number of hops) Path Finding Example: BFS (Breadth-first search) check all paths of length 1 check all paths of length 2 check all paths of length 3 etc ... stop when a path is found whose end is the destination Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Check all paths of length 1 Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Check all paths of length 1 Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Check all paths of length 2 Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Check all paths of length 2 Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Check all paths of length 2 - since end of path matches destination, we have found a solution. Wood Mountain Path Finding BFS advantages guaranteed to find shortest path can be easily modified to consider paths in order of increasing length, rather than number of links (not shown here) disadvantage: a bit trickier to program memory intensive Path Finding - Problems both path finding algorithms guaranteed to find a solution, if one exists however, they can be slow imagine a map with millions of possible points DFS may initially go in the wrong direction BFS will check many paths in the wrong direction, if they are closer than solution Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Suppose this link is connected to a map with many nodes. What if DFS tries this link first? Wood Mountain Path Finding - AI smart searching involves using a heuristic to improve its search capabilities simply stated, a heuristic provides a guess on which point it should try next the better the heuristic, the better the efficiency of the overall algorithm Path Finding - AI from previous example, suppose we knew the geographic (straight-line) distance between towns this could be computed from lat-lon coordinates we could modify our DFS algorithm when selecting a town amongst multiple choices, choose the one that is geographically closest to our destination Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Begin at starting position Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Choose a new point that you have not yet visited that is connected to you current point. Since we have two choices, choose the one that is geographically closest to Kincaid. Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie Choose a new point that you have not yet visited that is connected to you current point. Since we have thee choices, choose the one that is geographically closest to Kincaid. Wood Mountain Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie We have found a solution. Compare the number of points searched to our previous DFS solution. Wood Mountain Path Finding - AI our heuristic considerably reduced the number of points that we searched however, this approach is not guaranteed to work. Example: Ponteix Aneroid Kincaid Cadillac Mankota Val Marie DFS + heuristic search will try Mankota first, since it is geographically closer to Kincaid than Cadillac is. Wood Mountain Path Finding - AI when DFS is combined with a heuristic, it is known as a greedy search when BFS is combined with a heuristic (not shown), it is known as an A* search these algorithms collectively are known as best-first search.