1CS 1571 Intro to AIM. HauskrechtCS 1571 Introduction to AILecture 2Milos [email protected] Sennott SquareIntroduction (cont.)Problem solving by searchingCS 1571 Intro to AIM. HauskrechtCourse administriviaInstructor: Milos Hauskrecht5329 Sennott [email protected]: Swapna Somasundaran5422 Sennott [email protected] web page:http://www.cs.pitt.edu/~milos/courses/cs1571/2CS 1571 Intro to AIM. HauskrechtTextbookCourse textbook:Other widely used AI textbooks:Dean, Allen, Aloimonos: Artificial Intelligence. P. Winston: Artificial Intelligence, 3rded.N. Nillson: Principles of AI.Stuart Russell, Peter Norvig.Artificial Intelligence: A modern approach. 2ndedition, Prentice Hall, 2002CS 1571 Intro to AIM. HauskrechtArtificial Intelligence• The field of Artificial intelligence:– The design and study of computer systems that behave intelligently• AI programs:– Go beyond numerical computations and manipulations– Focus on problems that require reasoning (intelligence)• Two aspects of AI research:– Engineering • solving of hard problems– Cognitive• Understanding the nature of human intelligence3CS 1571 Intro to AIM. HauskrechtWhat is Artificial Intelligence ?Four different views on what makes an AI system!! Depends on what matters more in the evaluation.• Reasoning vs. Behavior– the computational process or the end-product matters• Human performance vs. Rationality– Compare against human model (with its weaknesses) or a normative “ideal” model (rational system)input output input outputCS 1571 Intro to AIM. HauskrechtAI todayAI is more rigorous and depends strongly on: applied math, statistics, probability, control and decision theoriesRecent theoretical advances and solutions:• Methods for dealing with uncertainty• Planning• Learning• Optimizations Applications:• Focus on partial intelligence (not all human capabilities)• Systems with components of intelligence in a specific application area; not general multi-purpose intelligent systems4CS 1571 Intro to AIM. HauskrechtAI applications: Software systems.Diagnosis of software, technical componentsAdaptive systems– Adapt to the user• Examples:– Intelligent interfaces(http://www.research.microsoft.com/research/dtg/))– Intelligent helper applications, intelligent tutoring systems– Web agents:•crawlers• softbots, shopbots (see e.g. http://www.botspot.com/ )CS 1571 Intro to AIM. HauskrechtAI applications: Speech recognition.• Speech recognition systems:– Hidden Markov models• Adaptive speech systems– Adapt to the user (training)– continuous speech– commercially available software (e.g. IBM http://www-3.ibm.com/software/speech/ )• Multi-user speech recognition systems– Restricted (no training)– Customer support:• Airline schedules, baggage tracking;• Credit card companies.5CS 1571 Intro to AIM. HauskrechtApplications: Space explorationAutonomous rovers, Telescope scheduling Analysis of dataintelligent probesCS 1571 Intro to AIM. HauskrechtAI applications: Medicine.• Medical diagnosis:– Pathfinder. Lymph-node pathology.– QMR system. Internal medicine.• Medical imaging http://www.ai.mit.edu/projects/medical-vision/– Image guided surgery (Eric Grimson, MIT) – Image analysis and enhancement6CS 1571 Intro to AIM. HauskrechtAI applications: Bioinformatics.• Genomics and Proteomics– Sequence analysis– Prediction of gene regions on DNA– Analysis of micro-array and proteomic MS profiles: find genes, proteins (peptides) that characterize a specific disease– Regulatory networksCS 1571 Intro to AIM. HauskrechtAI applications: Transportation.Autonomous vehicle control:• ALVINN (CMU, Pomerleau 1993) .• Autonomous vehicle• Driving across US• DARPA challenge (http://www.darpa.mil/grandchallenge/)– Drive across a Mojave desert course– 2004 – no vehicle finished the course– 2005 – 5 vehicles finished • The winner: Stanford team7CS 1571 Intro to AIM. HauskrechtAI applications: Transportation.• Vision systems:– Automatic plate recognition– Pedestrian detection (Daimler-Benz)– Traffic monitoring• Route optimizationsCS 1571 Intro to AIM. HauskrechtClassification of images or its parts8CS 1571 Intro to AIM. HauskrechtAI applications: Game playing. • Backgammon– TD-backgammon • a program that learned to play at the championship level (from scratch).• reinforcement learning• Chess– Deep blue (IBM) program beats Kasparov.• Bridge• Etc.CS 1571 Intro to AIM. HauskrechtAI applications. • Robotic toys– Sony’s Aibo(http://www.us.aibo.com/)• Humanoid robot– Honda’s ASIMO (http://world.honda.com/robot/)9CS 1571 Intro to AIM. HauskrechtOther application areas• Text classification, document sorting:– Web pages, e-mails– Articles in the news• Video, image classification• Music composition, picture drawing• Entertainment ☺CS 1571 Intro to AIM. HauskrechtTopics• Problem solving and search. – Formulating a search problem, Search methods, Combinatorial and Parametric Optimization.• Logic and knowledge representations. – Logic, Inference• Planning. – Situation calculus, STRIPS, Partial-order planners, • Uncertainty. – Modeling uncertainty, Bayesian belief networks, Inference in BBNs, Decision making in the presence of uncertainty.• Machine Learning – May be …10CS 1571 Intro to AIM. HauskrechtProblem solving by searchingCS 1571 Intro to AIM. HauskrechtExample• Assume a problem of computing the roots of the quadratic equationDo you consider it a challenging problem? 02=++ cbxax11CS 1571 Intro to AIM. HauskrechtExample• Assume a problem of computing the roots of the quadratic equationDo you consider it a challenging problem?Hardly we just apply the standard formula: aacbbx2422,1−±−=02=++ cbxaxCS 1571 Intro to AIM. HauskrechtSolving problems by searching• Some problems have a straightforward solution– Just apply the formula, or follow a standardized procedureExample: solution of the quadratic equation– Hardly a sign of intelligence• More interesting problems require search:– more than one possible alternative needs to be explored before the problem is solved – the number of alternatives to search among can be very large, even infinite.12CS 1571 Intro to AIM. HauskrechtSearch example: Traveler problem• Find a route from one city (Arad) to the other (Bucharest)CS 1571 Intro to AIM. HauskrechtExample. Traveler problem• Another flavor of