05 probabilistic robotics part1

in the chapter on probabilistic robotics what we have seen thus far is basically the math under the assumption that robots live in the ideal world where they have perfect sensors and perfect actuators unfortunately there's no such world and at least not in the real world that we live in and their robots are rather faced with imperfect sensors and imperfect actuators and this is what we are going to discuss today how we can actually deal with that and this is kind of like the core chapter of this course that what we are going to discuss today and the goal will be today and on Friday basically derive the basic underlying equations for perception and state estimation in in robotics this is actually that what is called probabilistic robotics there has been no exam thus far where the equation and the understanding of that equation was not asked just to give you an intuition about the importance of that equation although it's also sometimes obviously misunderstood that this is also not the only equation that is going to be asked in exams but what you can be assured is that this question this equation will be asked right it's a relatively long equation and the derivation will take approximately one hour but in the end the crash is relatively modular it has four components and all these components need to be understood and known and it's what we are going to discuss today how to actually arrive at that equation and then the next week's we will basically spend with implementing this equation and basically us answering the question of how can we realize this on a real robot to arrive at a robust navigation behavior for example and we implement these the this equation and in different forms in different ways for example for building maps of the environment for figuring out where the robot is given a map and then we will also discuss the application of this equation for the case where the robot does both at the same time building a map and figuring out where it is in the environment so this is a relatively important part of that chapter and also like if you take our time and we will derive this from first principles often thank all these equations would look like magically appearing but what we will do is we will basically start with the key concepts of probabilistic reasoning the actions we would start with the actions and from those derive that equation so the key idea of probablistic robotics is basically given the fact that robots live in a world in an imperfect world no perfect sense there's no perfect actuators that we are trying to arrive at an explicit representation of uncertainty which then allows us to reason about the uncertainty and which enables robot to do amazing things like for example doing something like active perception right to reduce for example the uncertainty in their belief about their own state or the state of the environment and also maybe perform actions that have minimum risk given the uncertainty that the robot actually can't be has and there are two concepts typically used in in in this context which is perception and there's the state estimation and the equation that we are going to arrive is the state estimation equation that we are going to use and that is underlying many state estimation processes in in real world but also it forms the basis for that what we call utility optimization because in principle like you do not have something like a given state that the system actually doesn't know in which state it or the environment is so it needs to calculate actions under uncertainty and this something there where this contact contacts a concept of utility optimization kicks in this is also something that you will study in the AI course so there is some overlap here the AI costs that will appear relatively at the end and a couple of weeks from now I think two to three weeks before the end of the term and we will also get to this relatively late and might be at the very very same time that we describe how this can actually be done be implemented like action generation based on uncertainty but in order to do this what we need to do first is figure out how we can represent uncertainty and deal with the uncertainty in the measurement processes and also in the action execution processes in order to obtain that what we call a probabilistic belief about the state of the system that and the system can be either the robot itself where it is or the environment so what is the state of the environment I told you that we are going to start with the basic principle so you basically look at the actions of probability theory which is which are depicted here like this are for actions basically that basically tell that all probabilities lie between 0 and 1 then in probabilities are expressed over so-called expressions we typically call like denote as a or B sometimes these different letters as well and I must admit that we am not entirely consistent in the in this presentation but take this as the opportunity to actual train your brain and establish associations between slightly inconsistent formulations you would also when you look at textbooks and there will also be slightly different formulations and uses of capital and lower case letter is for P and so on and so forth sometimes I admit it's slightly mixed up apologize but at the same time it also introduces the need for some flexibility so what you see is their probabilities need to lie between 0 and 1 it's amazing that people actually tend to forget this and even in scientific papers there are papers that contain a sentence like in this case we have signed the probability minus one not two whatsoever it actually doesn't exist and you will also get a little bit discussion about the fact that systems that use concepts deviating from these four actions over here Canada is actually very nice proof from and from an Italian mathematician that they in the long run perform sub-optimally and which means that it's a good advice to actually use calculate that or calculi that I actually compliant with these F for actions and if this statement aim that we have it's exactly the statement true so the constant true which is a true statement right then we assign the value 1 to it and if the statement is exactly false then we assign probability 0 to it and then there's this false axiom which in the very first place looks a little bit complicated but it somehow combines the basic operators in probability theory or in logic where we do have like the disjunction of two statements a or B and the conjunction of two statements a and B and and we combine this with some of the errors may take operations that we use for dealing with with numbers and it basically says probability of A or B is the probability of a plus the probability of B minus the probability of P of a of the probability of a and B and also like in the literature some people drop this last term over here and turns out that this is a mistake and in general all you need to know is that probabilities or there they appear sometimes there's a little bit magic there nothing else but counting we are basically doing nothing else but counting how often things appear and you can look at this for example and when you look at action 3 and if you come up with this very very simplistic counting argument they can you can easily that there is an intuition behind this subtraction of this term P of a and B over here so if you look at this figure for example so so let's assume that this is our domain over here and what we basically do is we like group the things in this we rearrange the optech objects in this domain or the in a way that basically we see here all cases in blue where a is true like all objects for which a is true and the the probability that a is true then it's basically nothing else but the size of this disk and in addition we group these objects for which B is true also in kind of like disk like form and they in this case have the very very same size but it actually doesn't matter that they have it even if this is distinct and we also arrange those where a and B is true for which a and B is true in a way that we have this overlapping area just by rearrangement right so what you can basically see is that the size of the blue disks relative to the domain is the probability that you when you pick a random object that a is true which basically is P of a in that domain and the size of the yellow disk it's a number of cases where B is true and we now look at the expression P of A or B these are basically all the objects for which either the expression A or the expression B is true which is nothing else but the area covered by the two circles but which is this area unfortunately is less than the sum of the two areas of the individual circles because if you'd like do if you consider this right what you do is when they have an overlap then it turns out that if you sum up the two individual sizes of the disks which would be P of a plus P of B then in this case you would count the overlapping area twice which means that you have to in order to come up with the correct value you need to subtract the overlapping area once right and this is why the disjunction of the tube A or B is basically the size of a size of B - the overlapping area and of course if the overlapping area is zero which means there's no object for which a and B is true then you can drop this term because it's zero then and which on the other hand means that the two disks are disjoint and don't have an overlap and so this basically the intuition behind this and then people also often argue but there is this there's this equation which basically says that P of not a which is the rest of the domain is 1 minus P of a obviously it's all the other objects in in this in this domain so a vise is not contained in the extras mathematicians and also statisticians are like idealists they actually want to have is the minimum description that is sufficient to express everything that you need to say about it about like then what a theory and this is why the actions are typically a minimum set of axioms that make sure that you can actually derive everything else from those actions and this famous like statement that P of a is 1 minus P of not a is basically it can easily be derived from those four actions that we saw before right and all we need to do is we need basically we need all the actions that we have seen thus far so P F we start with P of a or non a and from that we know that this is P of a plus P of non a plus 1 minus P of a and non-pay yeah this is basically nothing else but text replacement and so we were in this throughout this course we will very very often do nothing else but text replacement so if you think this is a super complex equation all you need to do in this case is textually replace B by not a and obviously the very same things should hold them facing this by not a P of a or not a P of a plus P of not a minus P of a and not a you very often do this just replacing text so you can actually also ask meri edit every child that can write and and reap letters and has no clue about statistics can do this text replacement right and this is something that we're going to do very very like often right and it's many cases it's nothing else but just replacing text no magic it's mechanically even a computer could do this that has no intuition about all the sir basically we do have P of a or not a is this equation over here that just text replacement a me know a logic a or not a is always true it's true and we also know that a and not a is always false there's no model for those expressions in propositional logic and we know that P of true is one one action and we know that P of force is zero the other action action and from that we get 1 is P of a plus P of non a and by a simple rearrange when you get P of a is 1 minus P of money of course you could add this to the actions but why doing so if you can have a more compressed description of that what you need for probability theory and basically everything else can be derived from that those actions all you need and that we will also do is we will basically introduce some terms and make some definitions from Vetri then which we then play around with so what this is all we do we basically use definitions in the remaining of this and then a player apply these actions and also reason about some of the being these type of terms that we introduced by the definitions usually like these constants that we use like X or a like denote that what we call a random variable and in the case that a is an expression saying like there's gonna be rain today whatsoever it's probably false to date for today no fortunately um but in this case we basically say this is a binary variable the statement can be either true or false but in general you can also have continuous variables for example if you think about robot localization you want to know where the robot is then this X would be if the robot lives on a plane a three-dimensional vector with u Britain which has like the component x coordinate y coordinate and orientation but it could also be that a variable that denotes in which room the robot might be alright and in this in this area down here and then in the ground floor of the soul this might be I don't know exactly you think six rooms are here right so X would be a six valued variable it could be the hallway this room the next room third room or one of the two lecture halls of course if you can't additionally at the bathroom then it's going to seven eight nine whatever you named but then you would have like a more higher valued but it's still discrete variable and if you go to the like the domain of positions then it's going to be a continuous variable a three-dimensional variable for example even and then what you basically the normal way of writing this down is if P of x equals small X it's basically the probability that this variable has a specific value formally whatever we would have to write down like the probability that the sentence today it's going to be raining is true equals true but we have often making appropriation when simply write down this this atomic value and when we say it's going to be raining today this is our atomic value so this basically the probability that the variable X takes on value X I usually we say this p of something is probability mass function we want to know what the probabilities are for the robot being in a specific room then could be one instance of that property mass function and in case it's a binary variable like we only need to specify one value the other one is directly given by the fact that over the domain that we have over all values that you don't know what could actually obtain the sum of those quantities in this crude case sums up to one and if I'm not wrong this is the case also in here so there we have like four rooms in this case and then overall the probability the robot must be anywhere in any of these four rooms in the case this is a continuous variable but then things are not that easy anymore because for any like because it's a dense domain floating-point numbers it's no longer discrete so which means that the probability that the robot is at a specific location zero zero and zero is virtually zero because simply because they deemed it's impossible to exactly achieve a certain coordinate and this is why you can actually only reason about the robot being in a certain interval which is then like in calculated as the the area under that probability mass function if you have to involved by integrating over from A to B over P of X so this is basically integrating over one of those functions for example so in general you decide between discrete and continuous cases robot localization for example is a continuous problem but we will also see discrete problems and we can also turn this robot localization problem into a discrete problem by simply discretizing the number of positions the robot could be it and I'm not thinking of this as being a continuous valued function but rather a discrete function we will see examples for that also in throughout this course but the constraint is that over all cases of X the sum of our P of X must be wondering for the continuous case meaning the area under that function must be one then there's this so-called joint probabilities now that we formulate is like that in this case it's this conjunction that we saw before that in this case and mighty and like in a might evaluate for multivalued variables this would be something like p of x equals x and y equals small Y then we typically write this down as P of X comma Y meaning P of x and y in the case that X doesn't tell us anything about Y meaning that those two disks that we have seen before basically disjoint but then this turns out to be exactly the probability of P of x times the probability of Y all right so this is so then they're basically independent and this concept of being independent is defined as the following basically we write down or dependency is like P of X given Y this is an something that or this is basically a definition now we write them and ever we write something like P of x given Y that basically stands for the for the case where we are interested in the probability of x given BR x we exactly know that Y is true so basically assume we that we got the information about Y and we now want to know what is the probability of X being true given we have the evidence Y so for example it could be the case that we are interested in the probability that it is raining outside given we have seen someone walking with an umbrella out there I thought the which is typically then different from the probability that it's raining outside right so which means that this expresses somehow the the dependency of X from Y and this is basically mathematically this is the defined as P of X given Y is P of x and y divided by P of Y there's nothing else but this definition on the other hand you can just like multiply this equation by P of Y which is nicer because P of Y could also be 0 and then we have P of x and Y is P of X given Y times P of Y I thought so this is basically a definition of the content conditional probability and obviously if x and y are independent meaning that Y the information of Y doesn't tell us anything about X that basically means that P of x given y equals P of X so for example if you want to know as to whether it's raining today and you they can look into the webcam and you see bad weather in Freiburg downtown or your new use of fatback vector cam and it's you see that it's raining out there then maybe there's a higher chance that it's raining here in five work downtown Freiburg compared to the the information where you see actually nice weather over there so the that which means that some of this information it's raining on felt back provides you with some more evidence about how the weather might be in 505 areas bias the information about how's the weather in Beijing right then this probably doesn't provide you with any information about all the weather and Freiburg is I do not know whether there's any dependency between the weather and Beijing or and Freiburg but I doubt that there is and it could even be so small that actually information about the weather in Beijing does not change the probability of me of being between sunshine in Freiburg at least to any measure that to any probability that we could measure so in that case we would argue that those two variables are independent so the weather in China doesn't provide you with any information about the weather in in Freiburg so the there to that there's one law that we are going to use throughout this which is called the law of total probability and this is basically that in the discrete case that P of x equals the sum of all over all Y of px of X given Y times P of Y which is basically the very same as this over here P of x equals the sum of all over all Y of P of X and y you know you might now argue why what that actually means if you think about this as a - well this is basically if you write this down right and say if you think about binary variables x and y right you can basically specify this those quantities by a two dimensional table and this would be for example in a two valued case you would have a table of like for example for x and y and you would have basically true/false and two true/false alright and this gives you a table with four entries and and in this you would no need to specify those four quantities in order to completely entirely describe P of x and Y for all cases yet you might have you could now take the values but you can also say like this is just a B C and D with the property that they all sum up to one so sum of a b c and d is one and if you're now interested in the probability that x is true like this one over here so how do you calculate that a plus b you basically take that row over here right and there you sum over both cases of y and take those a corresponding entries from the table this is basically what this law of total probability says or this Mitro marginalization you wouldn't even think about P R of Y being false what is that B plus D right you go of it that's summing over all X right P of y equals false and this is X values when you find it and they take the corresponding the true values of X so this basically that what is behind this marginalization rule its very same holds for the continuous case which is the nice part but in discrete case the discrete case is very easier to understand and this the law of total probability is nothing else but replacing this with a definition of conditional probability P of X and y is P of X given Y times P of Y just the definition nothing more yeah this one over here looks magic when you see for the first time but this is actually there's nothing complicated behind this and this over here is just applying the definition of the conditional probability to debt equation over here okay still there no magic right right believe me this is all not magic and this actually really relatively simple and from that you now can directly derive Bayes rule which is one of the most important equation or basic equation for probabilistic reasoning like if you write this down P of x and y conjunction in logic is symmetric meaning that P of X or a and B is a very same as B and a it's kind of like commutative right commutativity is that so basically meaning if you write it down like this p of x and y is P of X given Y times P of Y just by definition if we swap Y and X which is the same expression right then this is P of Y given X times P of X yeah and as X P of X and y is the very same of P of Y and X and we get arrived at that equation over here and once we we have this right hand side part now all we need to do is divide it by P of Y under the assumption that P of Y is nonzero then we arrive at P of X given Y is P of Y given x times P of X divided by P of Y stuff there's nothing else but follow just from this definition of conditional probability in these terms over here of specific names the left-hand side part is the likelihood this is a prior it's called the prior simply because here we this is called the posterior simply because we are interested in the the probability of x given we have we accumulated or information Y arrived so this is kind of like the what is the outcome of that information how does the information Y change our belief about X and here we don't have we have no Y available so here we put in the term what is a probability simply the prior value of the probability of X and P of Y down here is simply called the evidence actually it's symmetric to that but it's just for being able to distinguish the two like one basically calls this the prior and this down here the evidence this is actually the Bayes rule the there is one argument that will come up a couple of times in here so the interesting point is the interesting aspect of this equation is that this helps us to determine the probability of the state X given we know we have the information about the y is true for example and in the in this equation this Y down here is appears over here and what we can see is that this term is basically independent of of X there's no X in there and what one can now do is one can actually create an inference about that one in practice doesn't need to know this evidence down here in order to for example it is sufficient if we only have Y given X and P of X if you have those two values right for all combinations of X and y and all X in order to calculate the evidence down here this basically follows from the fact that if you think about this this term over here which basically says it's independent of of X right so it basically it's a consonant the very same for every X you can make an inference about how big this constant actually should be and simply because of the fact that if you look at the left hand side term if we sum over all X and calculate P of X given and take their values of P of X given Y what would be the the outcome and if you look at this equation over here or this this term you're going to turn this into an equation sum over all X P of X given Y okay we're gonna make it easier like let's look at the easier part some of our X P of X what is that one now let's assume that someone provides us with some evidence and we are now interested in what is the probability over all X P of X given this evidence any intuition P of Y that's actually not true yeah this but no no they mean that the point is that someone told us why from that we get an updated value at some some sort of a quantity that tells us what is the probability of X like let's let's think about this the simple example right we look outside the window we see someone walking with an umbrella out there we now ask the question what is the probability that it is raining given we see someone with an umbrella and what this equation tells us is what is it what about this this term set is you need to sum up over both both cases right so what is the probability that it is raining outside given we see someone with an ax Pirela plus the probability that is not raining outside given we see someone with an umbrella it's one so this basically it doesn't change anything right in this okay so basically we have the situation that it doesn't change anything regarding this we call this constraint the probability over all X given me know something actually stays one whatever whenever you have a probability distribution right the sum over all cases is always one even when you add that's what we what we call background here and this is I know that in this course it's often super confusing for students but maybe with this umbrella example you can see that this is actually all you get a slight intuition that this why the effect that we know why doesn't change this constraint that's over all X independently of what evidence we accumulate over all X the probabilities are always sum up to one you should not confuse this with this term this is not one not necessarily but this one is always one and now given we know of this you give me know that the sum over all X is one of P of X and y is one right this exactly tells us how there's what the quantity of P of Y should be if we know all the cases of Y given X and X because if we sum them up ignoring P of Y which is the same for all X the in fact with high likely it will get a sum that is different from one right and this P of Y does nothing else but acting as a constant that make sure that this left-hand side because it's the same for every X is independent of X so this constant cannot do anything else but making sure that the left hand side sums up to one over all X so if we don't know this right if for some reason we have no means for calculating this or nobody told us what P of Y would be we can still infer what P of Y is simply by calculating the sum over all these cases right it's basically what we need to do is calculate sorry for doing this here P of Y given X times P of X and we sum over all X these are the values that we have that we maybe get from whatsoever modeling the way we model the things and if you calculate this this is going to give us a sum which is likely different from one this is and and can you make an inference what not exactly it's 1 divided by P over is it P of Y maybe you're right let's see yeah we're going to go to the next slide I talked so much that my brain is actually I kind of like do the calculation in parallel but you're looking to be a seat on the next slide here like this is basically the constant is like the yeah it's P of Y you see you're right great you'll get an ice-cream for me once you medium ends that ok exactly so this is basically that what in art so this is it also follows from the law of total probability we look at this again like the law of total probability it's over here the only difference is that we now like swap X and y Tetris text replacement so we needed this entire hour long discussion to basically just do this text replacement but the motivation is that the argument here is that and this is what P what is typically confusing that we do not need this P of Y we do you know need to have the evidence and you can easily replace this by this constant over here and if we just take it have all the values available P of Y given X and P of X we can calculate this constant from from that and the algorithm that we are going to use is usually like this over here we are basically is summing up all these quantities then eta is 1 divided by this this auxiliary variable and then we are going to multiply the this with the this constant with the individual values and in this way obtain the exact values for every X we would see this in one of the algorithms it's not super necessary to understand this right now but it will appear later on actually in in one of the cases and this is why in many cases we are going to do that what we call normalization making sure that the probabilities sum up to 1 over all X so there's going to be a normalization step in in in some algorithms which exactly allows us to or frees us from the knowledge of the evidence which is sometimes hard to calculate and we will see this and the derivation as well and then basically get the and apply this basically this scheme over here not needed right now just as a motivation an additional equation is this over here which is the that is important it's Bayes rule with background knowledge we are not going to derive this but if you think about this equation over here make a careful look at this one over here all right here we basically compare this with this one over here so basically this says like the sum over all X P of x equals 1 and this doesn't change if we add information so the sum over all X P of X given Y is also 1 and you can regard this as as that some sort of background information that you can add to that equation over here we basically write we do have additional information but this doesn't change the basic concept namely that that sum equals to 1 and this is an this is also an important mechanism that basically every equation that you have can be extended by background information so it can add to the tree every equation like the bar right I basically add something then doesn't change and that equation and the very same holds also for Bayes rule and I it is actually a nice exercise exercise to derive this and for those of you I who are interested in playing around with this you can actually show that that this equation holds which is exactly Bayes rule it only differs by the fact that we add some additional information on the on the right hand side so it's P of X given Y and set that it's a very same F P of Y given X and that times P of X given that so we basically at this bar Z to the right hand side divided by P of Y given Z it's basically four for those of you are interested in it's actually relatively nice exercise calculating this it basically says that Bayes rule also halts when you actually add additional information basically doesn't change something about x and y about this general behavior you can simply explicitly add whatever you want as background you're not going to prove that but it's going to be super useful in in the rest and I think that now we're going to make a short break seven minutes that's some fresh air in and then continue [Music] go ahead so we will also now talk about these respect round information in the context of conditional probabilities and for example like you can see from this year also that you can simply add like background information to to every equation that you did that is available it's basically the very same so we have like P of x and y it's P of X times P of Y given that equivalently if the two are independent which basically it's a very same we can also drop why I've been x and y are independent even if you have background information set and this doesn't necessarily mean that when you have this of information over here that P of x and y are also conduct conditionally independent so it could be that knowledge about zet actually introduces in dependency between x and y so there's something that you need to take into account and you need to very carefully think about these independence assumptions or in dependencies or dependencies and it could be that p of x and y given that independent whereas they are not independent without the information about that so this is something that we would see also been when it comes to that we will actually make a proper statement about this but this is something that when obvious needs to take it to account and these in depends assumption are usually made for simplifying things particularly when you have like this year is a joint distribution and joint distributions you will you will discuss this in detail in the AI course these joint distributions have the problem that the size or the space that you need to represent those so now if you solve it so a two dimensional distribution before and there's actually a two dimensional table and for an n-dimensional table you would actually need a phone in dimensional distribution you need an n-dimensional table which means that the space that you need to represent this table depends depends exponentially on the dimension of your or the number of variables that you have you could you also think about this being X just being an n-dimensional state vector on n dimensional vector and having a probability distribution over an n-dimensional vector means that you need exposure space that is exponential in n and this is particularly problematic even though nowadays computers and because whatever is exponential actually something that relatively quickly grows out of bounds for therefore computers that we can ever imagine to build and this is why one often is interested in breaking joint distributions into individual distributions meaning that you can write down and the most in the ideal case like separating this into two one-dimensional distributions which n so which actually is save saves a lot in in in terms of memory and also computation and the more common cases that you make this assumption over here and we will see one particular example of this in just a few seconds where we can actually make the assumption that x and y are independent given Z but without that x and y are not independent we would see this in a few moments but this basically then helps us to make make efficient calculations for this probabilistic type of reasoning current mean in practice there's always called an independent and whenever you make this argument then you need to actually carefully argue that this independence is is actually given and if you cannot argue about this then what you will end up with is an equation that is a suboptimal description of what is going on what is going on and you will probably also obtain suboptimal results in your and your reasoning process what we're going to discuss today is very very simplistic situation we have a robot standing in front of a door or doorway and that what the robot needs to reason about is as to whether the door is open or closed and let's assume the robot has some type of sensor that allows it to infer like purr perception for one single measurement like what is the probability that the door is open and as a robot lives in a non deterministic world with respect to its sensors and it could be that in some case the robot actually sends our fires in a way that it says oh I think the door is open and in another case the sensor basically reports that the door is closed even though it is open so there might be arrows in that and what we are going to what we are interested in now is basically making that reasoning so they are basically iterating over measurement so that if like one measurement doesn't provide you with enough evidence or the risk for you is still too high then that what you can do is obtain multiple measurements so if you want to know if you are a piece of furniture fits into your kitchen and you measure it once right then and you think oh that might be tight and you maybe go there again and measure again and then from that you basically start inferring as to whether or not that system or that bit let's say dishwasher is going to fit into that into that part of your kitchen and and so you basically want to make sure that you do not spend your your money and in the end obtain an object that doesn't fit into your kitchen so that's what people typically do they measure multiple times until confidence is high enough to about the to make a proper decision in practice we can now use Bayes rule for calculating one day or flipping the the the the conditioner part of the equations if you remember correctly like so what we are oh let's first look at this problem in this robot we are typically interested in the probability that the door is open given the observation and in fact what this what the problem with this probability or with this term is that it's some are its prop it probably depends on the room the robot is standing in front of for example students might might say ok the the doors in the student lab are more often open simply because students are more often in the office and and whereas the professor's room it's mostly closed simply because the professor's never there so and that means that this robot that we need to make this inference and she needs to know in front of which door the robot is standing which means that you need to assess this quantity for single measurement in depends of or yeah depending on every individual door student rooms are more often open than professor rooms I thought the the other the other part like if you look at the other the other way of of that like P of Z given open that that equation has the advantage that it is independent of the particular room if all the doors are the same and let's assume that also that they are like I have the same colors and if you think about cameras or reflection values if you think about sound paste-like [Music] sensors like ultrasounds so let's assume that they are basically physically identical apart from the fact that one room is professors room and the other one is a student which means that i this process over here basically provides you with the probability that you obtain a particular measurement given the door is open and this obviously is independent of which door that is given all the doors are the same and this is why this actually sometimes more complicated to assess because you have to calculate this for every for every door individually if the behavior of the people is different it could even be someone who doesn't like open doors and you know that this is a person who never has a door or her door open then this probably would be a probability would be different right on the other hand like this one over here is independent of the door and it just describes the physical properties of the sensor and this is why when often cause this one causal and the other one diagnostic it's not you know it's not always the case but in principle one can argue that this part over here is easier to obtain and more effective to obtain and now the advantage now is that we are interested in this over here alright and this is the term we could actually learn this from data we will discuss this as well but in principle this is easier to obtain because it's independent of the door in many cases and the nice aspect now is the nicest feature now is that Bayes rule allows us to convert or to calculate one out of the other because like Bayes rule contains both terms yeah and it's basically nothing else but that the probably the probability of the doors open given in the measurement is the probability that we get this measurement giving the open door times and this is the professor versus a student right it's basically the prior that like which makes like the distinction between this measurement this term and this term over here it's exactly this prior about how often is the door open or not divided by P of Z the evidence and we know that we don't need this and this is nice because otherwise you also would need to have a distribution about how often do I get a specific measurement and basically throw this away right and this basically all you need in order to like once you have this P of Z given open and the nice aspect is you can easily obtain this by simply putting your sensor in front of the door opening the door and then cake statistics overall potential measurements that you get usually with approximations but that's what you do you put it into front in front of one of the doors and calculate the statistics are often you get every measurement that the the sensor can actually obtain you need to do some smoothing there to avoid that what is called overfitting something that we are going to discuss also in this course but once we have this distribution all you need to do is also count how often the individual doors open or not thank you measure like 100,000 times or how often you want to do this and basically get the statistics all right and once you have this you can calculate the probability that the door is open and given that possible specific measurement all right so let's go bet so it's basically everything is nothing else but counting and in this case you count how often you get a specific measurement given the doors open you also need to count how often the doors it's it's open and from that you get this diagnostic information what's the probability that the door is open given that particular measurement and and here let's assume this is what you obtain from your measurements P of that given open it's point six right so this is like how often you get this particular measurement you could even discretize your measurements if you have a distance sensor and say and ask like how often do I get something that is below three meters and how often do I get something that's below but it's beyond Earth oh it's three meters or more for example this would be just like two quantities that you need and they might be sufficient like in order to make that distinction and then like this would be the two like P of Z given opens point six and P of Z given closed is point three all right and we know like if you have no other information about the state of the door let's assume this is uniform like both states of the door have 0.5 then we do not need to do anything else but P of Oakland given that equals P of Z given open times P of open and you know that P of Y is to sum over all these cases up there which is P of Z given open times P of open plus P of that given closed times P of closed and all we need to do is and this is exactly this what happens in the normalization part and it this is P of Y its which is P of Z and in our case if you go back to this equation over here P offset now you see P of Z over here and P of Z is the sum over all both states of the door of P of Z given that state x the prior of they're probably probability of that state yeah no it's not it's just typically less than one because you have four cases right and it doesn't necessarily need to be one because it needs to be one over both cases of all cases offset so usually it's a very same that we had similar to that with what we had before it's also pretty confusing usually but P of Z the sum of all Y P of Z given Y is not necessarily one the other way the other thing is P of X is some Awards at P offset given Y this is one right the other one the other is not usually not true all right and if you assume those quantities then all you need to do is just fill in these the values and then you obtain like pure like 0.67 and if you compare this to the prior that the prior says okay we are we add of like uniform prior like every both cases have the same probability we are now in a situation that the probability that the door is open is actually higher than before so this measurement sum or increase the probability that the door is open okay as I mentioned I can practice we want to measure more often and now it comes as a little bit more complicated part right let's assume the robot attain obtains another measurement Z - all right what can we do with this new information then or in general we could ask the question let's assume we have n measurements and we want to know what is the state of the door given in measurements this is a general case derivation and now we are going to make a trick and we are going to make but all this looks super complicated but it's just textural replacement so what we're going to use this this Bayes rule with background information like for example like if you do P of a given B equals P of B given a times P of a divided by P of B all right Bayes rule with background information is P of a given B and C equals P of B given a and C times P of a given C divided by P of B given C okay it's nothing as but adding C to every term that we have okay but this is all you need to know it looks super complicated by this machine behind this is just a texture or replacement trick cursive base updating you're interested in estimating the state of the door given n measurements P of X gives add one to that and that one to that N and what we are now going to do is this part over here is a sequence of measurements and the replacement I asked you to do it's nothing else but like in this equation a equals x B equals in this case that we see that N and C equals that one to that n minus one correct any doubts visit super trivia there's actually it's a no-brainer oh and say so and you see this equation anything of my goodness but it's actually Bayes rule with background information and just this very very simplistic replacement trick and this is very very often the case in this probabilistic reasoning so these equations look magic and there's IP just definitions and textural replacement okay this is you know like in this we do have these equations over here and we are now going to do like to make a reasoning about this term over here right so what we had what we see there is the probability of the enth measurement given we know the state of the door and all the previous measurements all right and if you think about for example a camera or let's let's say a sound based sensor right so you made a sound cone and measured like get this measurement Z N and let's assume you have waited for an hour until like the echo is completely gone so there's actually no chance that you will actually be echo from any form of former sensation will actually get back into your receiver right and given your argument now is that given the state of the door giving you exactly know for example that the door is open this is the assumption the argument is that Zn is independent of all previous measurements if you think about this ultrasound it admits the sound right and given the state of the door right this day at the door the state of the door influences the measurement it depends on like when it's closed it might be different from when it's open but once we know the state of the door like it gets independent of all previous measurements actually this is not the case when we do not know the state of the door simply because like in in a normal situation like the measurements are somehow correlated in the sense that you would assume that if you don't move and if you don't change the world the next measurement is relatively similar to that what you have seen before so if I tell you that n minus 1 and tell you oh it was less than 3 meters then you would probably argue that ok the next one is more likely to be less than 3 meters then then more than 3 meters or more so this is basically the argument that if we know X and then actually the the state is going to be the the observation is independent from previous ones if you don't know X then it's actually not not the case basically X reduces the knowledge of X reduces this perception problem to the purely physical behavior of that sensor so and the the information about the deity or the Indian in the state of the door in capsules basically all or entails or contains all the information that all of the previous measurements so basically this is one assumption that one typically it does if you are not happy with this or if you don't live in a world where this is true then you cannot make this assumption and it is typically called a Markov assumption saying that Z n is independent of all previous measurements if we know X if we don't know X and this is actually not the case and that means basically that that N 1 to that n mean minus 1 do not provide us with any information about that n given we know the state of the door so which means that we can actually drop the those terms from this equation and we end up with P of Z n given X and then we have this term over here P of X give that end 2-1 to that n minus one and this evidence down here which is like an n-dimensional term which actually is exactly the pro Matic case that we do not know and it's extremely hard to model namely the probability of their n given that 1/2 that n minus 1 without knowing the state of the door basically the dependency of these measurements without additional information fortunately we have this constraint that the left hand side needs to sum up to 1 over all X so we can replace this term by this constant over here which just makes sure that the left hand side sums up to 1 we basically can drop this term down here and we end up with this equation ETA times P of zet and given x times this prior over here which is X given that 1 to the N minus 1 and every computer scientists now immediately sees a recursion over here because what we basically have you are interested in estimating the probability of x given that 1/2 that n minus 1 we reduces to the problem of like calculating the likelihood of the end measurement given X and have to multiply this with the probability of x given that 1/2 that n minus 1 so we basically reduce the problem size by 1 which is a recursion the next step that we do is we basically apply this argument recursively because structurally this completely is identical to this one over here it's a very same thing we take as background knowledge that one - that and - two very same argument all right which makes us in the end ending up with a constant that is a product of n normalization constants and we have this product over all from I to n over the likelihoods of this observation times given x times the probability of X prior probability meaning that we can actually replace this term over here which is a high dimensional probability distribution by the product of n 2-dimensional probability distributions this is done by your looking at as I mentioned before you look at the basically sum of all these values over all X and then this is basically the the one divided and you divide the entire every term by this sum all right so this ETA 1 to N is basically 1 divided by the sum of all those quantities over summed over all X you see this and for example it's the very same as in here like we basically take this value plus the opposite one for both cases is this this is X right we have x equals open x equals closed and we get this also for closed right they would basically calculate the very same for closed and the denominator stays the same you take both these these nominators sum them up and then this gives you basically the son we'd see this rest also in a second but this is also called recursive base in updating or you know like the posterior estimation I read this is just prior also it's contained so if you have a second measurement now right so basically can actually see realize this entirely and have P offset to give an open and B of P of site to give enclosed and then we can now calculate what's a probability or we use this as a prior like 2/3 that was the old quantity and then we do the very same as before just having z1 and z2 with this as prior and then we obtain like these quantities over here is just like entering like 2/3 into into here like this is the P of Z - given this is P of Z - game and open over here and then it's basically the sum of the two in here and this is like the outcome of of the entire calculation then so in this case that means that second measurement actually reduces the probability that the door is open that so this is basically the the idea how this is done and recursively like you only need to do like if you named from an implementation point of view you can go completely incrementally there I mean all you need to do is basically always only consider these these equations over here I the the denominator over here which is called which is calculated by this normalization process which is also in in this equation let me see this OP Nayyar sorry West this basically is the way you calculate this as was what's the description of how to calculate this this denominator this basically you see that this is actually there's some over those terms over here and we spread this out in the in this equation with the the or in this example with the door opening and so this is basically this where you see exactly this failure really is the sum over all these auxilary very values and same down here in this example where we actually calculated this this sum as you see here this is one time twenty vided by 4 plus 2 times 2 divided by 3 and this is the other quantities for the closed case alright so for those two basically over here and all you need to do is basically do this in in so this is this term over here is it's this one and the left-hand side is this one over here and in here you basically put the old priors which is now indicates that you have a second measurement the posterior of the form around that's basically that what you need to do there so at the end today we also want to incorporate actions and Ike and exons are needed because or incorporation because the robot might move right and when it comes to position estimation or might even use its arm to to open the door and the question is how can we deal with that and I give things of systems actually have actions to control them and actions are you know I never carried out with absolute certainty and typically actions increase uncertainty there are a few cases where you can also decrease uncertainty using actions but in practice in most cases they actually increase uncertainty so the in our like the probabilistic reasoning term we are basically interested in in a type of like equations like this this is what we assume to be given basically what it says is a distribution about how the world changes given an action so if you think about this door-opening example that situation that we are faced with this we do have the robot standing in front of the door we know the state of the door right so let's assume the door is closed the robot performs an action pre-programmed action and the most simplest case which is opening trying to open the door and what this statistic basically says then is how often does the robot succeed in doing so basically it says what is the probability that doors open given the robot the door was closed before and the robot executed it door opening action it's also very like usually you can be describe this by relatively simple distributions we will see this as come some sort of a in this example as a stochastic finite state automaton it's basically with this what what it is and that so the basically specifies the probability that the world changes in a corresponding way after executing action you all right so this is the closing door example all right and we are interesting now and in this opposite problem like what is the probably is that a door is closed given it was open before and the robot executed its door closing action but we can also ask the question what is a probability that the door is closed given the door it was closed before and the robot executed that action and you can for example specify this then entirely by by this by graph like this all right so if you think about here that probability that the door is closed given it executes at a closed door ik action as always why never changes so you're lucky it doesn't introduce noise it never goes from closed to open with the closing door action once it is closed but if it's open and it's executed it executes a closed door action and in 90 percent of all cases the idea what actually succeeds and in 10 percent of all the cases that the robot actually fails which means that we have a stochastic graph of there there types of the closing door action is successful in ninety percent of all cases so in practice you're now interested in yet we have two robot standing in front of the door and we are do not know the exact state of the door there's what we don't have but we have this distribution over here yet done we have done plenty of experiments confirm and we got these values right from the experiments and the situation now is that the robot stands in front of the door the state of which is next not exactly clear what we maybe have is a probability distribution that tells us what is the probability that the door is open or closed but we do not have the exact state all right so this term over here is actually never known to a robot and the reward over never knows what this what the exact state of the door is but we know that it makes sense that is somewhat easy to obtain we just put the robot in front of that door takes a door into two states and then at the robot operating the corresponding way and then do nothing else but counting so you can assume that we have this probability unfortunately right now it doesn't help us because the robot never exactly knows as to whether the doors open or closed but what we're interested in is like the state of the door given that action and without exactly knowing what the state of the door was and here now comes this gained is into the game this law of total probability which basically says this is nothing else but let's say take the discrete case but summing over all X Prime and P of X Prime and u times the prior of X Prime and in here what so it's basically nothing else but the equation of conditional probability in this case with background knowledge it's basically P of x equals some of our Y P of X given Y times P of Y right if you calculate this with background information let's say take P of X given that equals your sum over Y if you have X given Z and Y times P of Y given Z textual replacement in here u minus X stays the same that equals u and then this is what we obtained right we simply replay and X prime equals y nothing else but text replacement again the interesting aspect now is let's assume like that this is what we did we have the executed egg we are that we are interested in in the state of the door being X and the action you be having been executed by the robot from this like law of total probability with background knowledge we can actually infer this over here that this is exactly the sum over all X prime like P of x given you and X prime times P of X prime given you turns out that X prime was the state of the door before we executed that action all right so X prime actually happened before it was like the state of the world before the robot started to control its arm which means that it's actually independent of it right so the robot cannot change the past as we also cannot do meaning that the probability of the prior state of the door is independent of the action that that we executed the robot didn't should know X Prime and therefore it chose its action you independent of of that X prime which means that X prime is actually independent of you which means on the other hand that we can actually get rid of this u over there and now we are in this comfortable situation that we have a term over here P of X given U and X Prime and just need to multiply it that we have already for which we have statistics and we can use P of X prime which is a state of the door without any information and the belief about that just the prior state over of the door right which means that we can now do exactly this over here and then in this way reduce this to terms that we actually know and if you look at this like for the Eadie closing examples of the probability that the door is closed given we executed a closed door action P of closed given you NX Phi n times P of X prime by a state of the door right so it would be about both cases of the door P of being closed given you and the door was open before times P of open plus P of closed given you and closed or not open times P of not open and if you just and these are all quantities we have right this is see the priors that we got from our perception system it was 5/8 as far as I remember and it was it's 0.6 what's something and this we know that the closed door action succeeds in 90% of our cases when it's when it's open which meaning means that we actually get this and we end up with me having 15/16 just for the sake of like completeness we can also calculate the probability that the door is open after their action and then we just need to like enter the specific terms over here and then we end up with a quantity that this one's 1/16 which is nice because this is to potential States and some overall tools over both states was the probability of the state of the door needs to be 1 all right and just to give you an idea of about what's going to happen on Friday what we're going to do then is we're going to generalize this and the arrive a general equation and you're basically looking at we're doing the very same thing as you saw before saw today all right you're going to do this entirely on the blackboard on Friday and we're going to be done in and 45 minutes on Friday the general assumption here is or design general idea is that we like have a stream of data controls and observations that's a robot operates the door and measures it we did that what we call the sensor model which is this one term P of Z given X and the probability that the sensor provides us with a specific information given this particular state of of the system and we do have that what we call an action model which is P of X given U and X Prime it's basically thanked specifies how the world changes when we execute a particular action and we assume that there is a prior about the state of the system which in if you have no information it's a uniform distribution over all potential values of the state variable right so in general what we're interested in is estimating the posterior about the state of the system at time T which is P of XT given all the controls that we execute it and all the measurements that we had so we can for example consider this as a problem of robot navigator navigator around having a map of the environment and using its sensors to actually measure distances to two objects and moving around which are controls and what the robot now wants to know at every point in time where am i given I made executed this particular movement and obtained this particular measurement and this over time meaning I executed T movements and at every point and after every movement I observed this particular method this particular measurement so where am I now this is one of the problems and we call this a probablistic belief about the state of the system at time T she wondered I can quickly show you the entire creation to get an idea what is going to happen it are you curious or afraid even have a look at it on Friday yeah so thanks for coming today and see you on Friday and enjoy the nice weather today the rest of the day

Channel: 陈维

Views: 2,367

Rating: 5 out of 5

Keywords:

Id: kZNk4kSt7OM

Length: 85min 47sec (5147 seconds)

Published: Tue Dec 12 2017