AI-Unit1 Notes-final(AI-2017 ) PDF

Preview

Summary

Download AI-Unit1 Notes-final(AI-2017 ) PDF

Description

CS6659 -ARTIFICIAL INTELLIGENCE UNIT I -INTRODUCTION TO Al AND PRODUCTION SYSTEMS

9

Introduction to AI-Problem formulation, Problem Definition -Production systems, Control strategies, Search strategies.Problem characteristics, Production system characteristics Specialized production system- Problem solving methods -Problem graphs, Matching, Indexing and Heuristic functions –Hill Climbing-Depth first and Breath first, Constraints satisfaction - Related algorithms, Measure of performance and analysis of search algorithms. What is Artificial Intelligence? Artificial Intelligence (AI) is a branch of Science which deals with helping machines finding solutions to complex problems in a more human-like fashion. Maths, Psychology, Cognition, Biology and Philosophy, among many others. Our ability tocombine knowledge from all these fields will ultimately benefit our progress in the quest of creating an intelligent artificial being. Definition of Artificial intelligence 1. AI is the study of how to make computers do things which at the moment people do better. 2. AI is a field of study that encompasses computational techniques for performing tasks that apparently require intelligence when performed by humans. Systems that think like humans

Systems that think rationally

Machines with minds, in the full and literal

The study of mental faculties through the use

sense

of computational models. The study of the computations that make it

Systems that act like humans

possible to perceive, reason, and act. Systems that think rationally

The study of how to make computers do

Computational intelligence is the study and

things that, at the moment, people are better.

design

The art of creating machines that perform

behavior in artifacts

of

intelligent

functions that require intelligence when performed by people. The four approaches in more detail are as follows : (a) Acting humanly: The Turing Test approach o Test proposed by Alan Turing in 1950 o The computer is asked questions by a human interrogator.

agents.

Intelligent

The computer passes the test if a human interrogator, after posing some written questions, cannot tell whether the written responses come from a person or not. Programming a computer to pass, the computer need to possess the following capabilities:  Natural language processing to enable it to communicate successfully in English.  Knowledge representation to store what it knows or hears  Automated reasoning to use the stored information to answer questions and to draw new conclusions.  Machine learning to adapt to new circumstances and to detect and extrapolate patterns To pass the complete Turing Test,the computer will need  Computer vision to perceive the objects,and  Robotics to manipulate objects and move about. (b)Thinking humanly : The cognitive modeling approach We need to get inside actual working of the human mind : (a) through introspection – trying to capture our own thoughts as they go by; (b) through psychological experiments (c)Thinking rationally: The “laws of thought approach” The Greek philosopher Aristotle was one of the first to attempt to codify “right thinking”,that is irrefutable reasoning processes. His syllogism provided patterns for argument structures that always yielded correct conclusions when given correct premises—for example,”Socrates is a man;all men are mortal; therefore Socrates is mortal.”. These laws of thought were supposed to govern the operation of the mind;their study initiated a field called logic. (d)Acting rationally : The rational agent approach An agent is something that acts. Computer agents are not mere programs ,but they are expected to have the following attributes also : (a) operating under autonomous control, (b) perceiving their environment, (c) persisting over a prolonged time period, (e) adapting to change. A rational agent is one that acts so as to achieve the best outcome. AGENTS An AI system is composed of an agent and its environment. The agents act in their environment. The environment may contain other agents.

An agent is anything that can perceive its environment through sensors and acts upon that environment through actuators. 

A human agent has sensory organs such as eyes, ears, nose, tongue and skin parallel

to the sensors, and other organs such as hands, legs, mouth, for effectors.  A robotic agent replaces cameras and infrared range finders for the sensors, and various motors and actuators for effectors.  A software agent has encoded bit strings as its programs and actions.

Agent Terminology 

Performance Measure of Agent − It is the criteria, which determines how successful

an agent is.  Behavior of Agent − It is the action that agent performs after any given sequence of percepts. Percept − It is agent’s perceptual inputs at a given instance.  Percept Sequence − It is the history of all that an agent has perceived till date.  

Agent Function − It is a map from the precept sequence to an action.

The Structure of Intelligent Agents Agent’s structure can be viewed as − 

Agent = Architecture + Agent Program



Architecture = the machinery that an agent executes on.



Agent Program = an implementation of an agent function.

Different forms of Agent As the degree of perceived intelligence and capability varies to frame into four categories as,

A. B. C. D.

Simple Reflex Agents Model Based Reflex Agents Goal Based Agents Utility Based agents

(A)Simple Reflex Agents 

They choose actions only based on the current percept.



They are rational only if a correct decision is made only on the basis of current precept.



Their environment is completely observable.

Condition-Action Rule − It is a rule that maps a state (condition) to an action. Example: ATM system if PIN matches with given account number than customer get money. (B)Model Based Reflex Agents They use a model of the world to choose their actions. They maintain an internal state. Model − The knowledge about how the things happen in the world. Internal State − It is a representation of unobserved aspects of current state depending on percept history. Updating the state requires the information about − 

How the world evolves.



How the agent’s actions affect the world.

Example: Car driving agent which maintains its own internal state and then take action as environment appears to it.

Goal Based Agents They choose their actions in order to achieve goals. Goal-based approach is more flexible than reflex agent since the knowledge supporting a decision is explicitly modeled, thereby allowing for modifications. Goal − It is the description of desirable situations.

Example: Searching solution for 8-queen puzzle. Utility Based Agents They choose actions based on a preference (utility) for each state. Goals are inadequate when − There are conflicting goals, out of which only few can be achieved.  Goals have some uncertainty of being achieved and you need to weigh likelihood of 

success against the importance of a goal.  Example: Millitary planning robot which provides certain plan of action to be taken.

Properties of Environment The environment has multifold properties − 

Discrete / Continuous − If there are a limited number of distinct, clearly defined,

states of the environment, the environment is discrete (For example, Cross world,8Queen puzzle.); otherwise it is continuous (For example, driving, flight control).  Observable / Partially Observable − If it is possible to determine the complete state of the environment at each time point from the percepts it is observable; (for example: Image analysis, Puzzle game) otherwise it is only partially observable (For example: Pocker game, Military planning).



Static / Dynamic − If the environment does not change while an agent is acting, then it is static;(For example:8-queen puzzle) otherwise it is dynamic(For example:

Cardriving, Tutor).  Deterministic / Non-deterministic − If the next state of the environment is completely determined by the current state and the actions of the agent, then the environment is deterministic (For example: Image Analysis); otherwise it is nondeterministic (For example:Boat driving, cardriving, flight control). 

Episodic / Non-episodic − In an episodic environment, each episode consists of the agent perceiving and then acting. The quality of its action depends just on the episode

itself. Subsequent episodes do not depend on the actions in the previous episodes.  For example: blood testing for patient, card games) Episodic environments are much simpler because the agent does not need to think ahead.(Ex:Redinery controller, chess with clock) Problem Formulation & Solving—Introduction 

Goal formulation Often the first step in problem-solving is to simplify the performance measure that the agent is trying to maximize. Formally, a "goal" is a set of desirable world-states. "Goal formulation" means ignoring all other aspects of the current state and the performance measure, and choosing a goal. Example: if you are in Arad (Romania) and your visa will expire tomorrow, your goal is to reach Bucharest airport.

Problem Spaces and Search Building a system to solve a problem requires the following steps, -

Define the problem. This definition must include precise specifications of what

the initial situations will be as well as what final situations constitute acceptable solutions to the problem. -

Analyse the problem thoroughly for some features may have a dominant affect

on the chosen method of solution; - Isolate and represent the background knowledge needed in the solution of the problem; - Choose the best problem solving techniques in the solution. Defining the Problem as state Search To understand what exactly artificial intelligence is, we illustrate some common problems. Problems dealt with in artificial intelligence generally use a common term called 'state'. A state represents a status of the solution at a given step of the problem solving procedure. The solution of a problem, thus, is a collection of the problem states. The problem solving

procedure applies an operator to a state to get the next state. Then it applies another operator to the resulting state to derive a new state. The process of applying an operator to a state and its subsequent transition to the next state, thus, is continued until the goal (desired) state is derived. Such a method of solving a problem is generally referred to as state space approach For example, in order to solve the problem play a game, which is restricted to two person table or board games, we require the rules of the game and the targets for winning as well as a means of representing positions in the game. The opening position can be defined as the initial state and a winning position as a goal state, there can be more than one. legal moves allow for transfer from initial state to other states leading to the goal state. However the rules are far too opioids in most games especially chess where they exceed the number of particles in the universe 10. Thus the rules cannot in general be supplied accurately and computer programs cannot easily handle them. The storage also presents another problem but searching can be achieved by hashing. The number of rules that are used must be minimized and the set can be produced by expressing each rule in as general a form as possible. The representation of games in this way leads to a state space representation and it is natural for well organized games with some structure. This representation allows for the formal definition of a problem which necessitates the movement from a set of initial positions to one of a set of target positions. It means that the solution involves using known techniques and a systematic search. This is quite a common method in AI. Formal description of a problem -

Define a state space that contains all possible configurations of the relevant objects, without enumerating all the states in it. A state space represents a problem in terms of states and

Operators that change states - Define some of these states as possible initial states; - Specify one or more as acceptable solutions, these are goal states; -

Specify a set of rules as the possible actions allowed. This involves thinking

about the generality of the rules, the assumptions made in the informal presentation and how much work can be anticipated by inclusion in the rules.

The control strategy is again not fully discussed but the AI program needs a structure to facilitate the search which is a characteristic of this type of program. Example: The water jug problem: There are two jugs called four and three ; four holds a maximum off our gallons and three a maximum of three gallons. How can we get 2 gallons in the jug

four. The state space is a set of ordered pairs giving the number of gallons in the pair of jugs at any time ie (four, three) where four = 0, 1, 2, 3, 4 and three = 0, 1, 2, 3. The start state is (0, 0) and the goal state is (2, n) where n is a don't care but is limited to three holding from 0 to 3 gallons. The major production rules for solving this problem are shown below: Initial

condition

goal

comment

1 (four, three) if four < 4

(4,three)

fill four from tap

2 (four,three) if three< 3

(four,3)

fill three from tap

3 (four,three) If four > 0

(0,three)

empty four into drain

4 (four,three) if three > 0

6 (four,three) if four+three0

(three,0)

empty three into four

8 (four,0) if four>0

(0,four)

empty four into three

9 (0,2)

(2,0)

empty three into four

5 (four,three) if four+three...