лекция 7. неопределенность-введение

Views:
 
Category: Entertainment
     
 

Presentation Description

Неопределенность-Введение

Comments

Presentation Transcript

Introducing Uncertainty (It is not the world that is imperfect, it is our knowledge of it) R&N: Chap. 3, Sect 3.6 + Chap. 13:

1 Introducing Uncertainty (It is not the world that is imperfect, it is our knowledge of it) R&N: Chap. 3, Sect 3.6 + Chap. 13

Slide 2:

2 So far, we have assumed that: World states are perfectly observable,  the current state is exactly known Action representations are perfect,  states are exactly predicted We will now investigate how an agent can cope with imperfect information We will also study how limited resources (mainly time) affect reasoning Occasionally, we will consider cases where the world is dynamic

Introductory Example:

3 Introductory Example Goal A robot with imperfect sensing must reach a goal location among moving obstacles (dynamic world)

Slide 4:

4 air bearing gas tank air thrusters Robot created at Stanford’s ARL Lab to study issues in robot control and planning in no-gravity space environment

Model, Sensing, and Control :

5 Model, Sensing, and Control The robot and the obstacles are represented as disks moving in the plane The position and velocity of each disc are measured by an overhead camera every 1/30 sec x y robot obstacles

Model, Sensing, and Control :

6 Model, Sensing, and Control The robot and the obstacles are represented as disks moving in the plane The position and velocity of each disc are measured by an overhead camera within 1/30 sec The robot controls the magnitude f and the orientation a of the total pushing force exerted by the thrusters x y a f robot obstacles

Motion Planning:

7 Motion Planning The robot plans its trajectories in configuration  time space using a probabilistic roadmap (PRM) method t x y Obstacle map to cylinders in configuration  time space

But executing this trajectory is likely to fail ...:

8 But executing this trajectory is likely to fail ... The measured velocities of the obstacles are inaccurate Tiny particles of dust on the table affect trajectories and contribute further to deviation  Obstacles are likely to deviate from their expected trajectories Planning takes time, and during this time, obstacles keep moving  The computed robot trajectory is not properly synchronized with those of the obstacles  The robot may hit an obstacle before reaching its goal [Robot control is not perfect but “good” enough for the task]

But executing this trajectory is likely to fail ...:

9 But executing this trajectory is likely to fail ... The measured velocities of the obstacles are inaccurate Tiny particles of dust on the table affect trajectories and contribute further to deviation  Obstacles are likely to deviate from their expected trajectories Planning takes time, and during this time, obstacles are moving  The computed robot trajectory is not properly synchronized with those of the obstacles  The robot may hit an obstacle before reaching its goal [Robot control is not perfect but “good” enough for the task] Planning must take both uncertainty in world state and time constraints into account

Dealing with Uncertainty:

10 Dealing with Uncertainty The robot can handle uncertainty in an obstacle position by representing the set of all positions of the obstacle that the robot think possible at each time (belief state) For example, this set can be a disc whose radius grows linearly with time t = 0 t = T t = 2T Initial set of possible positions Set of possible positions at time 2T Set of possible positions at time T

Dealing with Uncertainty:

11 Dealing with Uncertainty The robot can handle uncertainty in an obstacle position by representing the set of all positions of the obstacle that the robot think possible at each time (belief state) For example, this set can be a disc whose radius grows linearly with time t = 0 t = T t = 2T The robot must plan to be outside this disc at time t = T

Dealing with Uncertainty:

12 Dealing with Uncertainty The robot can handle uncertainty in an obstacle position by representing the set of all positions of the obstacle that the robot think possible at each time (belief state) For example, this set can be a disc whose radius grows linearly with time The forbidden regions in configuration  time space are cones , instead of cylinders The trajectory planning method remains essentially unchanged

Dealing with Planning Time :

13 Dealing with Planning Time Let t=0 the time when planning starts. A time limit d is given to the planner The planner computes the states that will be possible at t = d and use them as the possible initial states It returns a trajectory at some t < d , whose execution will start at t = d Since the PRM planner isn’t absolutely guaranteed to find a solution within d , it computes two trajectories using the same roadmap: one to the goal, the other to any position where the robot will be safe for at least an additional d . Since there are usually many such positions, the second trajectory is at least one order of magnitude faster to compute t = 0 t = d planning execution

Are we done?:

14 Are we done? Not quite ! The uncertainty model may itself be incorrect, e.g.: There may be more dust on the table than anticipated Some obstacles have the ability to change trajectories But if we are too careful, we will end up with forbidden regions so big that no solution trajectory will exist any more So, it might be better to take some “risk” The robot must monitor the execution of the planned trajectory and be prepared to re-plan a new trajectory

Are we done?:

15 Are we done? The robot must monitor the execution of the planned trajectory and be prepared to re-plan a new trajectory Execution monitoring consists of using the camera (at 30Hz) to verify that all obstacles are at positions allowed by the robot’s uncertainty model If an obstacle has an unexpected position, the planner is called back to compute a new trajectory.

Experimental Run:

16 Experimental Run Total duration : 40 sec X

Experimental Run:

17 Experimental Run

Is this guaranteed to work?:

18 Is this guaranteed to work? Of course not : Thrusters might get clogged The robot may run out of air or battery The granite table may suddenly break into pieces Etc ... [Unbounded uncertainty]

Sources of Uncertainty:

19 Sources of Uncertainty

The Real World and its Representation:

20 The Real World and its Representation Real world Agent’s conceptualization (  representation language) 8-puzzle 3x3 matrix filled with 1, 2, .., 8, and ‘empty’

The Real World and its Representation:

21 The Real World and its Representation Real world Agent’s conceptualization (  representation language) Blocks world Logic sentences using propositions like Block(A), On(A,B), Handempty, ... and connectives

The Real World and its Representation:

22 The Real World and its Representation Real world Agent’s conceptualization (  representation language) Air-bearing robot navigating among moving obstacles Geometric models and equations of motion

Who provides the representation language? :

23 Who provides the representation language? The agent’s designer As of today, no practical techniques exist allowing an agent to autonomously abstract features of the real world into useful concepts and develop its own representation language using these concepts Inductive learning techniques are steps in this direction, but much more is needed The issues discussed in the following slides arise whether the representation language is provided by the agent’s designer or developed over time by the agent

First Source of Uncertainty: The Representation Language:

24 First Source of Uncertainty: The Representation Language There are many more states of the real world than can be expressed in the representation language So, any state represented in the language may correspond to many different states of the real world, which the agent can’t represent distinguishably A B C A B C A B C On(A,B)  On(B,Table)  On(C,Table)  Clear(A)  Clear(C)

First Source of Uncertainty: The Representation Language:

25 First Source of Uncertainty: The Representation Language 6 propositions On(x,y), where x, y = A, B, C and x  y 3 propositions On(x,Table), where x = A, B, C 3 propositions Clear(x), where x = A, B, C At most 2 12 states can be distinguished in the language [in fact much fewer, because of state constraints such as On(x,y)  On(y,x)] But there are infinitely many states of the real world A B C A B C A B C On(A,B)  On(B,Table)  On(C,Table)  Clear(A)  Clear(C)

 An action representation may be incorrect ...:

26  An action representation may be incorrect ... Stack(C,A) P = Holding(C)  Block(C)  Block(A)  Clear(A) D = Clear(A), Holding(C) A = On(C,A), Clear(C), Handempty is likely not to have the described effects in case 3 because the precondition is “incomplete” A B C A B C A B C On(A,B)  On(B,Table)  On(C,Table)  Clear(A)  Clear(C) 1 3 2

... or may describe several alternative effects:

27 ... or may describe several alternative effects Stack(C,A) P = Holding(C)  Block(C)  Block(A)  Clear(A) [If On(A,x)  (x  Table)] D = Clear(A), Holding(C) A = On(C,A), Clear(C), Handempty D = Holding(C), On(A,x) A = On(C,Table), Clear(C), Handempty, On(A,Table), Clear(A), Clear(x) A B C A B C A B C On(A,B)  On(B,Table)  On(C,Table)  Clear(A)  Clear(C) E 1 E 2 1 3 2 OR

Observation of the Real World:

28 Observation of the Real World Real world in some state Percepts On(A,B) On(B,Table) Handempty Interpretation of the percepts in the representation language Percepts can be user’s inputs, sensory data (e.g., image pixels), information received from other agents, ...

Second source of Uncertainty: Imperfect Observation of the World:

29 Second source of Uncertainty: Imperfect Observation of the World Observation of the world can be: Partial , e.g., a vision sensor can’t see through obstacles (lack of percepts) R 1 R 2 The robot may not know whether there is dust in room R2

Second source of Uncertainty: Imperfect Observation of the World:

30 Second source of Uncertainty: Imperfect Observation of the World Observation of the world can be: Partial, e.g., a vision sensor can’t see through obstacles Ambiguous , e.g., percepts have multiple possible interpretations A B C On(A,B)  On(A,C)

Second source of Uncertainty: Imperfect Observation of the World:

31 Second source of Uncertainty: Imperfect Observation of the World Observation of the world can be: Partial, e.g., a vision sensor can’t see through obstacles Ambiguous, e.g., percepts have multiple possible interpretations Incorrect

Third Source of Uncertainty: Ignorance, Laziness, Efficiency:

32 Third Source of Uncertainty: Ignorance, Laziness, Efficiency An action may have a long list of preconditions, e.g.: Drive-Car: P = Have(Keys)  Empty(Gas-Tank)  Battery-Ok  Ignition-Ok  Flat-Tires  Stolen(Car) ... The agent’s designer may ignore some preconditions ... or by laziness or for efficiency, may not want to include all of them in the action representation The result is a representation that is either incorrect – executing the action may not have the described effects – or that describes several alternative effects

Representation of Uncertainty:

33 Representation of Uncertainty Many models of uncertainty We will consider two important models: Non-deterministic model : Uncertainty is represented by a set of possible values , e.g., a set of possible worlds, a set of possible effects, ...  The next two lectures Probabilistic model : Uncertainty is represented by a probabilistic distribution over a set of possible values  The following two lectures

Example: Belief State:

34 Example: Belief State In the presence of non-deterministic sensory uncertainty, an agent belief state represents all the states of the world that it thinks are possible at a given time or at a given stage of reasoning In the probabilistic model of uncertainty, a probability is associated with each state to measure its likelihood to be the actual state 0.2 0.3 0.4 0.1

What do probabilities mean?:

35 What do probabilities mean? Probabilities have a natural frequency interpretation The agent believes that if it was able to return many times to a situation where it has the same belief state, then the actual states in this situation would occur at a relative frequency defined by the probabilistic distribution 0.2 0.3 0.4 0.1 This state would occur 20% of the times

Example:

36 Example Consider a world where a dentist agent D meets a new patient P D is interested in only one thing: whether P has a cavity, which D models using the proposition Cavity Before making any observation, D’s belief state is: This means that D believes that a fraction p of patients have cavities Cavity  Cavity p 1-p

Where do probabilities come from?:

37 Where do probabilities come from? Frequencies observed in the past, e.g., by the agent, its designer, or others Symmetries, e.g.: If I roll a dice, each of the 6 outcomes has probability 1/6 Subjectivism, e.g.: If I drive on Highway 280 at 120mph, I will get a speeding ticket with probability 0.6 Principle of indifference: If there is no knowledge to consider one possibility more probable than another, give them the same probability

Non-Deterministic vs. Probabilistic:

38 Non-Deterministic vs. Probabilistic If the world is adversarial and the agent uses probabilistic methods, it is likely to fail consistently If the world in non-adversarial and failure must be absolutely avoided, then non-deterministic techniques are likely to be more efficient computationally In other cases, probabilistic methods may be a better option, especially if there are several “goal” states providing different rewards and life does not end when one is reached

Uncertainty and Errors:

39 Uncertainty and Errors The uncertainty model may itself be incorrect Representing uncertainty can reduce the risk of errors, but does not eliminate it entirely !! Execution monitoring is required to detect errors and (hopefully) fix them [ closed-loop execution] What to monitor? How to fix errors?

What to monitor?:

40 What to monitor? Action monitoring: Check preconditions before executing an action and effects after Not very efficient (e.g., a precondition may have been false for a while) Plan monitoring: Check the preconditions of the entire remaining plans  Triangle tables

Key-in-Box Problem:

41 Grasp-Key-in-R 2 P = In(Robot,R 2 )  In(Key,R 2 ) D =  A = Holding(Key) Lock-Door P = Holding(Key) D = Unlocked(Door) A = Locked(Door) Move-Key-from-R 2 -into-R 1 P = In(Robot,R 2 )  Holding(Key)  Unlocked(Door) D = In(Robot,R 2 ), In(Key,R 2 ) A = In(Robot,R 1 ), In(Key,R 1 ) Put-Key-Into-Box P = In(Robot,R 1 )  Holding(Key) D = Holding(Key), In(Key,R 1 ) A = In(Key,Box) Key-in-Box Problem R 1 R 2

Triangle Table:

42 Triangle Table Grasp-Key-in-R 2 Move-Key-from-R 2 -into-R 1 Lock-Door Put-Key-Into-Box In(Robot,R 2 ) In(Key,R 2 ) In(Robot,R 2 ) Unlocked(Door) Holding(Key) Holding(Key) In(Robot,R 1 ) Holding(Key) Locked(Door) In(Key,Box) Plan: Grasp-Key-in-R 2 , Move-Key-from-R 2 -into-R 1 , Lock-Door, Put-Key-Into-Box to achieve Locked(Door)  In(Key, Box)

Triangle Table:

43 Triangle Table Grasp-Key-in-R 2 Move-Key-from-R 2 -into-R 1 Lock-Door Put-Key-Into-Box In(Robot,R 2 ) In(Key,R 2 ) In(Robot,R 2 ) Unlocked(Door) Holding(Key) Holding(Key) In(Robot,R 1 ) Holding(Key) Locked(Door) In(Key,Box) Propositions from the initial state that are necessary to the applicability of actions in the plan and the achievement of the goal

Triangle Table:

44 Triangle Table Grasp-Key-in-R 2 Move-Key-from-R 2 -into-R 1 Lock-Door Put-Key-Into-Box In(Robot,R 2 ) In(Key,R 2 ) In(Robot,R 2 ) Unlocked(Door) Holding(Key) Holding(Key) In(Robot,R 1 ) Holding(Key) Locked(Door) In(Key,Box) Propositions achieved by Grasp-Key-in-R 2 that are necessary to the applicability of subsequent actions and the achievement of the goal

Triangle Table:

45 Triangle Table Grasp-Key-in-R 2 Move-Key-from-R 2 -into-R 1 Lock-Door Put-Key-Into-Box In(Robot,R 2 ) In(Key,R 2 ) In(Robot,R 2 ) Unlocked(Door) Holding(Key) Holding(Key) In(Robot,R 1 ) Holding(Key) Locked(Door) In(Key,Box) Propositions contained in initial state or achieved by actions of the plan that are necessary to the achievement of the goal

Triangle Table:

46 Triangle Table Grasp-Key-in-R 2 Move-Key-from-R 2 -into-R 1 Lock-Door Put-Key-Into-Box In(Robot,R 2 ) In(Key,R 2 ) In(Robot,R 2 ) Unlocked(Door) Holding(Key) Holding(Key) In(Robot,R 1 ) Holding(Key) Locked(Door) In(Key,Box) 3 rd kernel of the plan: If all the propositions in it are true, the agent can proceed to execute the 3 rd action of the plan (Lock-Door)

Triangle Table:

47 Triangle Table Grasp-Key-in-R 2 Move-Key-from-R 2 -into-R 1 Lock-Door Put-Key-Into-Box In(Robot,R 2 ) In(Key,R 2 ) In(Robot,R 2 ) Unlocked(Door) Holding(Key) Holding(Key) In(Robot,R 1 ) Holding(Key) Locked(Door) In(Key,Box) 5 rd kernel of the plan: If all the propositions in it are true, the goal is achieved

Execution Monitoring with Triangle Tables:

48 Execution Monitoring with Triangle Tables Repeat: Observe the world and identify the largest k such that all the propositions in the k th kernel are true If k = 0 then re-plan Else execute the k th action of the plan Actions that fail are repeated Actions that are not needed are skipped

But ...:

49 But ... Repeating an action that failed assumes that it may succeed next time. But what if the agent picked the wrong key in R 2 ? Either the agent has more knowledge or sensors than it used so far, and it’s time to use them Or it doesn’t have any of these, and it has no choice – fail or call another agent [I do the same when my car does not start and I can’t figure out why]

On-Line Search:

50 On-Line Search Sometimes uncertainty is so large that actions need to be executed for the agent to know their effects Example: A robot must reach a goal position. It has no prior map of the obstacles, but its vision system can detect all the obstacles visible from a the robot’s current position

Slide 51:

51 Assuming no obstacles in the unknown region and taking the shortest path to the goal is similar to searching with an admissible (optimistic) heuristics

Slide 52:

52 Assuming no obstacles in the unknown region and taking the shortest path to the goal is similar to searching with an admissible (optimistic) heuristics

Slide 53:

53 Assuming no obstacles in the unknown region and taking the shortest path to the goal is similar to searching with an admissible (optimistic) heuristics Just as with classical search, on-line search may detect dead-ends and move to a more promising position (~ node of search tree)

Suggestion:

54 Suggestion It’s time to refresh your memory on probability theory: axioms of probability random variable joint distributions conditioning independence [R&N: Chap. 13, Sect. 13.3-6] We will be using probabilities in a few lectures

authorStream Live Help