L1B Introduction to AI concepts.pdf

UNIT- I Introduction: AI problems, Agents and Environments, Structure of Agents, Problem Solving Agents Basic Search Strategies: Problem Spaces, Uninformed Search (Breadth First, Depth- First Search, Depth-first with Iterative Deepening), Heuristic Search (Hill Climbing, Generic Best-Fi...

UNIT- I Introduction: AI problems, Agents and Environments, Structure of Agents, Problem Solving Agents Basic Search Strategies: Problem Spaces, Uninformed Search (Breadth First, Depth- First Search, Depth-first with Iterative Deepening), Heuristic Search (Hill Climbing, Generic Best-First, A*), Constraint Satisfaction (Backtracking, Local Search) Introduction: Artificial Intelligence is concerned with the design of intelligence in an artificial device. The term was coined by John McCarthy in 1956. Intelligence is the ability to acquire, understand and apply the knowledge to achieve goals in the world. AI is the study of the mental faculties through the use of computational models AI is the study of intellectual/mental processes as computational processes. AI program will demonstrate a high level of intelligence to a degree that equals or exceeds the intelligence required of a human in performing some task. AI is unique, sharing borders with Mathematics, Computer Science, Philosophy, Psychology, Biology, Cognitive Science and many others. Although there is no clear definition of AI or even Intelligence, it can be described as an attempt to build machines that like humans can think and act, able to learn and use knowledge to solve problems on their own. Sub Areas of AI: 1) Game Playing Deep Blue Chess program beat world champion Gary Kasparov 2) Speech Recognition PEGASUS spoken language interface to American Airlines' EAASY SABRE reservation system, which allows users to obtain flight information and make reservations over the Page 5  telephone. The 1990s has seen significant advances in speech recognition so that limited systems are now successful. 3) Computer Vision Face recognition programs in use by banks, government, etc. The ALVINN system from CMU autonomously drove a van from Washington, D.C. to San Diego (all but 52 of 2,849 miles), averaging 63 mph day and night, and in all weather conditions. Handwriting recognition, electronics and manufacturing inspection, photo interpretation, baggage inspection, reverse engineering to automatically construct a 3D geometric model. 4) Expert Systems Application-specific systems that rely on obtaining the knowledge of human experts in an area and programming that knowledge into a system. a. Diagnostic Systems: MYCIN system for diagnosing bacterial infections of the blood and suggesting treatments. Intellipath pathology diagnosis system (AMA approved). Pathfinder medical diagnosis system, which suggests tests and makes diagnoses. Whirlpool customer assistance center. b. System Configuration DEC's XCON system for custom hardware configuration. Radiotherapy treatment planning. c. Financial Decision Making Credit card companies, mortgage companies, banks, and the U.S. government employ AI systems to detect fraud and expedite financial transactions. For example, AMEX credit check. d. Classification Systems Put information into one of a fixed set of categories using several sources of information. E.g., financial decision making systems. NASA developed a system for classifying very faint areas in astronomical images into either stars or galaxies with very high accuracy by learning from human experts' classifications. 5) Mathematical Theorem Proving Use inference methods to prove new theorems. 6) Natural Language Understanding AltaVista's translation of web pages. Translation of Catepillar Truck manuals into 20 languages. Page 6  7) Scheduling and Planning Automatic scheduling for manufacturing. DARPA's DART system used in Desert Storm and Desert Shield operations to plan logistics of people and supplies. American Airlines rerouting contingency planner. European space agency planning and scheduling of spacecraft assembly, integration and verification. 8) Artificial Neural Networks: 9) Machine Learning Applications of AI: AI algorithms have attracted close attention of researchers and have also been applied successfully to solve problems in engineering. Nevertheless, for large and complex problems, AI algorithms consume considerable computation time due to stochastic feature of the search approaches 1. Business; financial strategies 2. Engineering: check design, offer suggestions to create new product, expert systems for all engineering problems 3. Manufacturing: assembly, inspection and maintenance 4. Medicine: monitoring, diagnosing 5. Education: in teaching 6. Fraud detection 7. Object identification 8. Information retrieval 9. Space shuttle scheduling Building AI Systems: 1) Perception Intelligent biological systems are physically embodied in the world and experience the world through their sensors (senses). For an autonomous vehicle, input might be images from a camera and range information from a rangefinder. For a medical diagnosis system, perception is the set of symptoms and test results that have been obtained and input to the system manually. Page 7  2) Reasoning Inference, decision-making, classification from what is sensed and what the internal "model" is of the world. Might be a neural network, logical deduction system, Hidden Markov Model induction, heuristic searching a problem space, Bayes Network inference, genetic algorithms, etc. Includes areas of knowledge representation, problem solving, decision theory, planning, game theory, machine learning, uncertainty reasoning, etc. 3)Action Biological systems interact within their environment by actuation, speech, etc. All behavior is centered around actions in the world. Examples include controlling the steering of a Mars rover or autonomous vehicle, or suggesting tests and making diagnoses for a medical diagnosis system. Includes areas of robot actuation, natural language generation, and speech synthesis. The definitions of AI: a) "The exciting new effort to make b) "The study of mental faculties computers think... machines with minds, through the use of computational in the full and literal sense" (Haugeland, models" (Charniak and McDermott, 1985) 1985) "The automation of] activities that we "The study of the computations that associate with human thinking, activities make it possible to perceive, reason, such as decision-making, problem solving, and act" (Winston, 1992) learning..."(Bellman, 1978) c) "The art of creating machines that perform d) "A field of study that seeks to explain functions that require intelligence when and emulate intelligent behavior in performed by people" (Kurzweil, 1990) terms of computational processes" (Schalkoff, 1 990) "The study of how to make computers "The branch of computer science do things at which, at the moment, that is concerned with the people are better" (Rich and Knight, 1 automation of intelligent behavior" 99 1 ) (Luger and Stubblefield, 1993) Page 8 The definitions on the top, (a) and (b) are concerned with reasoning, whereas those on the bottom, (c) and (d) address behavior. The definitions on the left, (a) and (c) measure success in terms of human performance, and those on the right, (b) and (d) measure the ideal concept of intelligence called rationality Intelligent Systems: In order to design intelligent systems, it is important to categorize them into four categories (Luger and Stubberfield 1993), (Russell and Norvig, 2003) 1. Systems that think like humans 2. Systems that think rationally 3. Systems that behave like humans 4. Systems that behave rationally Human- Rationall Like y Cognitive Science Approach Laws of thought Approach Think: “Machines that think like humans” “ Machines that think Rationally” Turing Test Approach Rational Agent Approach Act: “Machines that behave like humans” “Machines that behave Rationally” Cognitive Science: Think Human-Like a. Requires a model for human cognition. Precise enough models allow simulation by computers. b. Focus is not just on behavior and I/O, but looks like reasoning process. c. Goal is not just to produce human-like behavior but to produce a sequence of steps of the reasoning process, similar to the steps followed by a human in solving the same task. Laws of thought: Think Rationally a. The study of mental faculties through the use of computational models; that it is, the study of computations that make it possible to perceive reason and act. Page 9  b. Focus is on inference mechanisms that are probably correct and guarantee an optimal solution. c. Goal is to formalize the reasoning process as a system of logical rules and procedures of inference. d. Develop systems of representation to allow inferences to be like “Socrates is a man. All men are mortal. Therefore Socrates is mortal” Turing Test: Act Human-Like a. The art of creating machines that perform functions requiring intelligence when performed by people; that it is the study of, how to make computers do things which, at the moment, people do better. b. Focus is on action, and not intelligent behavior centered around the representation of the world c. Example: Turing Test o 3 rooms contain: a person, a computer and an interrogator. o The interrogator can communicate with the other 2 by teletype (to avoid the machine imitate the appearance of voice of the person) o The interrogator tries to determine which the person is and which the machine is. o The machine tries to fool the interrogator to believe that it is the human, and the person also tries to convince the interrogator that it is the human. o If the machine succeeds in fooling the interrogator, then conclude that the machine is intelligent. Rational agent: Act Rationally a. Tries to explain and emulate intelligent behavior in terms of computational process; that it is concerned with the automation of the intelligence. b. Focus is on systems that act sufficiently if not optimally in all situations. c. Goal is to develop systems that are rational and sufficient Page 10  Agents and Environments: Fig 2.1: Agents and Environments Agent: An Agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. ✓ A human agent has eyes, ears, and other organs for sensors and hands, legs, mouth, and other body parts for actuators. ✓ A robotic agent might have cameras and infrared range finders for sensors and various motors foractuators. ✓ A software agent receives keystrokes, file contents, and network packets as sensory inputs and acts on the environment by displaying on the screen, writing files, and sending network packets. Percept: We use the term percept to refer to the agent's perceptual inputs at any given instant. Percept Sequence: An agent's percept sequence is the complete history of everything the agent has ever perceived. Agent function: Mathematically speaking, we say that an agent's behavior is described by the agent function that maps any given percept sequence to an action. Agent program Internally, the agent function for an artificial agent will be implemented by an agent program. It is important to keep these two ideas distinct. The agent function is an abstract Page 11 mathematical description; the agent program is a concrete implementation, running on the agent architecture. To illustrate these ideas, we will use a very simple example-the vacuum-cleaner world shown in Fig 2.1.5. This particular world has just two locations: squares A and B. The vacuum agent perceives which square it is in and whether there is dirt in the square. It can choose to move left, move right, suck up the dirt, or do nothing. One very simple agent function is the following: if the current square is dirty, then suck, otherwise move to the other square. A partial tabulation of this agent function is shown in Fig 2.1.6. Fig 2.1.5: A vacuum-cleaner world with just two locations. Agent function Percept Sequence Action [A, Clean] Right [A, Dirty] Suck [B, Clean] Left [B, Dirty] Suck [A, Clean], [A, Clean] Right [A, Clean], [A, Dirty] Suck … Page 12 Fig 2.1.6: Partial tabulation of a simple agent function for the example: vacuum-cleaner world shown in the Fig 2.1.5 Function REFLEX-VACCUM-AGENT ([location, status]) returns an action If status=Dirty then return Suck else if location = A then return Right else if location = B then return Left Fig 2.1.6(i): The REFLEX-VACCUM-AGENT program is invoked for each new percept (location, status) and returns an action each time A Rational agent is one that does the right thing. we say that the right action is the one that will cause the agent to be most successful. That leaves us with the problem of deciding how and when to evaluate the agent's success. We use the term performance measure for the how—the criteria that determine how successful an agent is. ✓ Ex-Agent cleaning the dirty floor ✓ Performance Measure-Amount of dirt collected ✓ When to measure-Weekly for better results What is rational at any given time depends on four things: The performance measure defining the criterion of success The agent’s prior knowledge of the environment The actions that the agent can perform The agent’s percept sequence up to now. Omniscience ,Learning and Autonomy: We need to distinguish between rationality and omniscience. An Omniscient agent knows the actual outcome of its actions and can act accordingly but omniscience is impossible in reality. Rational agent not only gathers information but also learns as much as possible from what it perceives. If an agent just relies on the prior knowledge of its designer rather than its own percepts then the agent lacks autonomy. A system is autonomous to the extent that its behavior is determined its own experience. A rational agent should be autonomous. Page 13  E.g., a clock(lacks autonomy) No input (percepts) Run only but its own algorithm (prior knowledge) No learning, no experience, etc. ENVIRONMENTS: The Performance measure, the environment and the agents actuators and sensors comes under the heading task environment. We also call this as PEAS(Performance,Environment,Actuators,Sensors) Page 14  Environment-Types: 1. Accessible vs. inaccessible or Fully observable vs Partially Observable: If an agent sensor can sense or access the complete state of an environment at each point of time then it is a fully observable environment, else it is partially observable. 2. Deterministic vs. Stochastic: If the next state of the environment is completely determined by the current state and the actions selected by the agents, then we say the environment is deterministic 3. Episodic vs. nonepisodic: The agent's experience is divided into "episodes." Each episode consists of the agent perceiving and then acting. The quality of its action depends just on the episode itself, because subsequent episodes do not depend on what actions occur in previous episodes. Episodic environments are much simpler because the agent does not need to think ahead. 4. Static vs. dynamic. If the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent; otherwise it is static. 5. Discrete vs. continuous: If there are a limited number of distinct, clearly defined percepts and actions we say that the environment is discrete. Otherwise, it is continuous. Page 15