SLAM-Course - 01 - Introduction to Robot Mapping (2013/14; Cyrill Stachniss)

okay so then after this kind of production what you're going to see here um a shirred deduct the course so what I would like to tell you today or what the goal of this lecture today is not that you gain any very in-depth knowledge about something but you should have a pretty good idea what you can expect from that course so what are the topics that we're going to cover why is it relevant what we are doing that's something you could actually be able to see today so first what if you looked over the title of our course which is robot mapping the first two questions which may arise what the robot what is mapping so robot is first device which move through the environment and in most cases this device is equipped with sensors actually all robot that we consider here equip the sensors also there are robots which are actually basically free of sensors of so poor sensing capabilities that it's Mullis sensing free but that's nothing what we're interested in here so we look into mobile robots that move to the environment that means they have some kind of wheels some kind of legs some kind of wings or propellers or some means to actually move through the environment so we're looking into mobile robotics here mobile devices that drive through the environment fly through the environment swim whatever you can imagine and the second thing that actually we look into here is devices with sensors so some people call actually what sensors on wheels which is actually in some sense true depending on the application that you do it may be sufficient to just have sensors on wheels and some very limited computation power depending on the application that you focus on you may want to have a more powerful robot but the most important things that we actually use here in this course are big perceptions and also the controls that are sent to the robot so if the robot says drive a meter forward and send this to the motors and the motors drive a meter forward or approximatively a meter forward that's a valuable information whenever the robot has a camera and takes a picture of some part of the environment or it has a laser scanner installed and gets proximity measurements to the closest obstacle that's kind of our sensor information and we want to exploit the controls and the sensor information to gain knowledge you want to gain knowledge about the that's where we come to the second part of the title which is mapping we want to look into robot that actually build a map of the environment that can be map it's kind of a very flexible term that can be some representation some model of the environment doesn't need to be a metric map that you may know or your city map or your subway map that you're used to a different kind of Maps geometric topological maps it's just some representation that the robot uses in order to model the environment gain collect knowledge about the environment and the end uses for decision-making any question at that point okay so these are terms which occur in the context of robot mapping some of them are closely related to robot mapping some are less related but still influenced by that course so they start with state estimation state estimation means we have a state let's say the position of the robot in the environment were the position of the landmark in a given reference frame and we want to estimate this quantity of the state the state the world is in the world state we want to estimate it because we don't know perfectly we just get sensor data the sensor data is noisy most of the cases actually always the modes can be very small but often the noise is not that small and we want to estimate that state so for example we want to know where the robot is or we want to know where lent market from the environment so this is what often said with state estimation and one way to do state estimation is a base to the reclusive base filter that you may have seen so if you give noisy observations you have nosey controls the our techniques we'll look into this recursive based filter in more detail next week it's one way to do state estimation so to estimate what's the state of the world the world can be whatever you want to model about the world so the position of the robot the position of landmarks whatever it is you're interested in this is closely related to the second problem over here localization localization is actually a part or an application of state estimation in most cases it means we want to estimate where is our device our sensor our robot so where is it in the world we want to estimate the location of the robot we often talk about the term posed here which is often referred to as the location x y coordinate for example as well as the orientation they are the angular orientation of the robots where the robot look which direction of it look at something which is often referred to as pose where its location often means just the XY coordinate this is different in different fields depending on whatever in robotics it's kind of coined into a kind of a standard to do it like that with other fields other fields which do mapping which are related to what we're doing here then we may use a completely different terminology but that's kind of let's a standard thing most people use in robotics okay then we have mapping mapping in the robotics sense is often referred to as kind of having sensor data and I want to estimate the model the model of the environment so I want to map the environment in a lot of aspects this mapping means that you know where your sensor is this is not the case in the general methane framework but in robotics if you talk about mapping we typically mean we know where the sensor is we just want to estimate the quantities that we see for example we we know the position of of a sensor here and I wanted for example with this laser measurement device I want to measure what's where is this wall with respect to the position of the of the laser pointer here and then that's a measurement and I just want to estimate where that wall it's something which is mapping if I don't know where the sensor is that's typically a combination combined problem which includes localization telling where these devices and mapping telling well that wall is so therefore in robotics often people use it to remapping assuming to know the position where the robot or weather sensor was and if you don't know that then you actually end up in slam slam sense for simultaneous localization and mapping that means you want to simultaneously estimate the position of your center of your and the state of the environments of the state of the environment therefore people sometimes or often distinguish between mapping and slam also if you talk in sloppy terms mapping would mean everything because they and you are often interested in the map of the environment therefore the course is also called robot mapping also it's a bit sloppy into in the terminology that we often use in robotics okay the next thing which is important to navigation navigation means a heavy device or robot which can make its own decision and maybe I tell that robot hey go whatever in that corner over there and the Robo needs to decide they actually navigate he around here or should I take a left and then turn right over there to end up at the desired target location the vacation is not a topic that we are going to address in this course here but navigation strongly relies on slam were on mapping on having a map went on also knowing you are required to know where the vehicle is not apply in a pass and navigate somewhere so navigation is not explicitly addressed in this course but one of the key motivation factors of that courses that we want to have models about the environment and estimate the location of the robot in the environment in order to carry out navigation actions we may do other things we may manipulate objects with the manipulator and we the robot may not move at all then you also need to know what the environment looks like around that robot so whatever decision you're making it's often very helpful to have a model of the environment at hand that's kind of one of the motivations for that course here and then motion planning is kind of very tightly coupled with with navigation so you really want to plan where to go which may satisfy some constrains amazing to find the optimal motion sequence to reach your goal location you may plan motions of it as I said manipulators before so it may go even beyond whatever just moving a rigidbody in the XY space can be more complex but again that's nothing we are going to address in this course but that these are techniques which actually are benefit from having an environment model so we will actually look into these four aspects here where slam is the most important stuff that we cover but if we solve slamming also soft vocalization we also solve and mapping and in order to solve the slam problem you need state estimation it's kind of the rough picture that we are going to address here any questions so far is please yeah yeah so as I said in motion planning you can actually plan the trajectory or a sequence of states that the system should be in in order to reach a certain goal configuration so it can be manipulators let's see more armours here and they arm should be how should I get get my arm in this hole over here that's a big emotion playing from you wouldn't typically call that navigation navigation is typically device which moves in the X Y theta X but rotation or and three-dimensional space of physically guiding a robot from one location to another location but they are very tightly coupled so most navigation system use motion planning algorithms like never a star or variants of a star that you may have used that you can use for ups for guiding vehicle from location a to location B but is not restricted to that you can also use planning for other kinds of problems that you're going to solve so it's kind of what I told you before was kind of more the core robotics perspective of that but generally you're absolutely right any other questions okay so let's go a little bit more to the details of what a slam and kind of be a bit morph but not yet formal but formalize it a bit more so we end up in a more formal description in the end so what we interested in is actually computing the different positions of the robot at different points in time it's kind of a trajectory or a path that the robot took as well as a map of the environment or model of the environment there are different types of environments environment models that you can imagine will just catch them on a high level at least during this course today and but that's kind of our main objective and then we have the problem recipe for localization which means estimating the robots location so this actually means estimating the trajectory so where has robot been at different points in time and then we have mapping which is actually try to build a map so yeah whatever the environment model and slam simultaneous localization means doing this at the same time and in reality these are localization the mapping problem um I don't want say they don't exist but in the end you always need to solve the slam problem unless you have some external absolutely great whatever tool sensor if God told you where the robot was at different point in times yes you can do mapping and if the robot told you exactly what the environment looks like yes you can do localization but quite often these are things which strongly interact with each other so if you don't have a model given by someone which you assume to be right you typically need to do some form of slam to solve both problems at the same time it may be that the environment model that you have is sufficiently good or sufficiently accurate they can say okay I ignore the rest and just do localization this case it exists or if you say that's such an accurate whatever X my robot moves on I don't know a rail and a perfectly know it is on the rail with some other means that I can focus on the more challenging task of just modeling what the environment looks like in this case you can also separate that a little bit but in reality you are mostly faced with simultaneous localization and mapping even if you're only interested in what the environment looks like or where the robot actually is okay so just to make the point why to illustrate the different properties of these problems so what you see here is a robot a different point in time so T equals 1 T equals 2 T equal 3 the robot move through the environment on some trajectory we typically don't consider this is in continuous process but at discrete points in time say every second or every time the robot takes a sensor measurement and then we have other things here which are these stars and these stars should illustrate landmarks that means something the robot can observe and can recognize so if you have a robot which drives around in front of all university on the green you will it may have a sensor tech trees so every tree will be a landmark so then you have whatever 23 is here in front of our building then you have 20 landmarks and the robot may estimate the location of those trees of those landmarks and then it can also estimate its own poles relative to these landmarks ok so these guys are landmarks and these dashed lines here should illustrate observations of those landmarks so the robot is here it can see these two landmarks that are going to see you can see only this line mark if they're able to see it can see these two landmarks and this small dotted line should actually represent the trajectory that the robot was taking and I'm just considering these three points in time okay now we look at the localization localization was we know what the environment looks like but we don't know where the robot is it means we know the position of those landmarks so God told us the position of those landmarks so we know those stars are here and then we need to estimate where was the robot so we add es to estimate those poses and this may look like this so in the beginning the robot actually observed that he acquired well then the robot was driving and it can you should deviated from its path so this is kind of the the true path sorry it's a true path and this is what the robot estimate so it's kind of the grayish ones or here the estimates of these two things so here the robot thought it turned left but in reality it turned right so maybe the air or one of its wheels lost air so the diameter diameter of one wheel gets smaller and the little bit gets drift to one side maybe one explanation for these stupid behavior here turning to the left Lindner what makes an observation is okay here that I'm actually actually be here say hmm but there is no landmark so the line works actually here so there's kind of a correction step that actually drags the robot towards its real pose saying where the road was si si the leg mark is one meter away so did my measure but according to the map it should be only 50 centimeters away it's okay there is a mismatch between what I measured let's exhale this kind of what comes from this correction down here and then the robot continuous driving and then it make another correction may end up here at the current pose at the end that's kind of the localization problem for what rights the environment you integrate its control command you get an estimate of where the robot probably is then you get an observation or what sees some length marks in the environment and then can kind of correct its pose and the correction or the amount of Correction depends on how accurate is it sensor how accurate is this motion execution if a very very accurate motion execution but a very very stupid or bad noisy sensor you will probably trust your motion has to make much more than your sensing data the other hand if you have a very poor sensor for example elect robots so the humanoids say - it's pretty hard to get a good odometry or post estimate from the way they with robots walk he will probably rely much more on your sensor data ok that's that then we can actually look into mapping so and this is what the world looks like in reality and the robot knows its pose so it's kind of mapping example gnosis someone tell the road where it is at different points in time so it would take subserve ations and these observations maybe here that gray stars the road will move through the environment so it will create a map and say hey this feature is here this feature is here it continues driving a feature is here and this feature is here as you may observe here again this estimate about the world stage is not perfect I mean the position of those landmarks are not exactly where those networks are but this is just a result from your noisy sensor data and in the ideal case you know what the uncertainty of your sensor is so you know let's say in 95% of the cases I have an error of up to 10 centimeters from my measured distance in this case you could actually draw some uncertainty ellipses like you would do would be a Gaussian estimate actually draw around your estimate and say the true location of the landmark is very likely to be whatever within a certain bound that's what mapping is about ok in slam again that's a set up what happened in reality the robot started here measured the location of those landmarks these are these two guys they continuous driving again has this turned to the lab can drift to the left they it measures the other landmark so this is snow this over here and since it doesn't know where this let Magazine reality it just adds this land back to its map to its self built map and it cannot do this correction step or only maybe it's some to some degree that the robot in the localization example then it continues driving so here the estimated trajectory of the robot will be this one although in reality the robot took this movement and the grey stars is what the estimated map would look like and this is substantially different from what the real map looks like so there's always an error in our estimates or all realistic situations there's an error in the in the estimate what you may have seen here or guest here is that actually the map estimate depends on the localization accuracy so this map is less accurate than this map over here where and you knew the pose of the robot and if I know where the and so this pulls estimate where I have this correction here so this guy's dragged down here it's more accurate than the poles estimate of this line context so whenever I know what the environment looks like I can better estimate my pose and if I have a good estimate of about my pose I can actually build a better map that's also why this is often referred to as a chicken or egg problem so a map is needed for localizing the robot and a good pose estimate is also needed in order to solve the mapping problem so there's a dependency between what the environment looks like or the model of the environment and how well the robot can localize itself which again influences on how accurate my model there's this this infant or this suggests that this is a kind of a joint estimation task we cannot fully decouple localization from mapping we actually have to solve this at the same point in time that's a reason whereas our main motivation for the slam problem and if you do that then we can actually so we can solve the same problem we have the most important let's say tools at hand or means at hand in order to solve the autumns navigation problem having a robot which I can just specify its goal location and the robot is able to navigate there you know to do that it needs to know what the environment looks like and it needs to know where it isn't the environment in order to reach its goal occasion and so solving this ramp flam problem has a direct impact on the applications that we can actually build with mobile robots and there are typical applications or it's kind of having a working slam system at hand is still something that a lot of robots actually miss and as one of the limiting factors today - let's say dramatically increase the number of robots for service tasks on factory floors so for example reflected floors this problem is typically solved by just screwing the robot to the ground so the robot cannot move then you don't have a localization problem it really don't have a mapping problem and that's a way how kind of industrial robotics solve this problem but if as soon as you have more flexible production lines where let's say manipulators are on wheels and can drive freely in the environment this really becomes an issue and even for other applications so if you have every kind of whatever logistics service task where robot needs to transport goods from A to B this technique is needed you can argue I you can build a map once manually and give it to the robot knowledge of localization it's partially true but still if someone changes something in the environment if new goods arrive and the pass is blocked or what needs to replan how can all this be taking to account so having a working slime system which solves mapping and localization at the same point in time is not something which is just academically interesting like an interesting from an academic standpoint but it's also a direct impact on real-world applications and today there are some systems which can actually solve the same problem quite well sometimes this is compromised between having a good estimation technique and making some assumptions about the environment or require having certain requirements like a certain type of length mark SATA or ensure to be always visible so some constraints if maybe need to be fulfilled on a factory floor and if these constraints are fulfilled the system is guaranteed to not guarantee but it's very likely to work so there compromises between that but slam is still an open an interesting problem so there are different applications that you can envision so for example in your home environment you can think about your your Hoover autonomous Hoover robot you may have whatever a Roomba robot at home which is kind of the one of the cheapest robots you can have for moving your ground and this robot actually has also an interesting strategy that it says I agree ignored this lamp problem I just do random walk I just drive randomly for the environment and as time goes to infinity I will have cleaned that room the advantage is if your room is small this time it doesn't really need infinity doesn't need to approach infinity to actually clean your room but it's kind of the very uninformed very very trivial approach whenever you want to have some systematic cleaning or some guarantees you can provide then you would need to go beyond that gets a little bit more tricky for lawn mowers so items lawn mowing is also something there you can actually know by go to whatever every big Home Depot like store and for whatever less than 2,000 euro you will actually find an autonomous lawnmower they get a little bit better in that sense also that typically don't explicitly build a map but they typically need want to know where their charging station is because at some point in time they need to go back so again here's kind of they typically do a compromise here so you have to install some wires in your garden whenever the robot drives of this wire connected okay I shouldn't go here so therefore you can prevent your robot whatever falling in your pool or whatever it can happen and it also helps orbit maybe drive back to its to its to its base station in forever for example recharge so they are compromised but there's the the the lawn mowing industry right now it's really interested in getting that slam problem solved in a really really robust manner because they wonder what the people need to install this is wire below them their lawn as that allows the robot to walk say to work safely or operate safely so there's real interest in kind of getting rid of that just putting the robot they're switching it on maybe telling them don't go here don't go there but then go ahead and start start working without having whatever an expensive or time-consuming installation which needs to be done and so that's another application the other applications like unmanned aerial vehicles surveillance tasks for example were monitoring tasks after disaster missions or for for example patrolling and estimating the quality of the ground crops crop sensing is also kind of a big agricultural application for autonomous airplanes or autonomous helicopters so different kinds of surveillance tasks actually require to know where the robot actually is the advantages for flying out of vehicles at least if they are a larger scale GPS is a pretty good pose estimation technique so they actually a lot of the problems simplify if you have those means at hand but you may have applications where you don't want to rely on GPS or where GPS is simply not available underwater robotics so reef monitoring tasks this is a pretty well studied not well studied but intensively investigated field in Australia for example there's the australian centre field robotics in Sydney which have a lot of boats a lot of underwater robots that actually inspect reefs that met the ground and they will look for example also estimate how does the reef structure or the ground structure changes over time over the years and so they want to be able to monitor the ground build accurate models of the ground actually relate missions over different years estimating hopefully the same part of the environment then we have underground applications whatever mind applications exploring mines they are other applications which are archaeological interests we want to have accurate 3d reconstructions of some small underground channels past catacombs whatever it is and you also have space applications where you want to map an environment and to exploration missions in in space so these are typically typical examples that you see so what you see here is actually the evolution robotics mint now bought by iRobot which is one of the kind of Swiffer style robot so it kind of a Swiffer towel down here throw it dredge through the environment and systematically cleans your cleans your floor this is one of your lawns lights and underwater robots at the Austrian centre field robotics monitoring the ground you have space exploration missions or that's actually exploration of an abandoned mine in close to Pittsburgh done back Sebastien's run so your typical applications that you find also brought you a small video that's actually one of the showcase we use of the main system just play works the secret is the revolutionary Northstar navigation system simply place the Northstar beacon in the area you want to clean and it works like indoor GPS allowing mint to track where it cleans so it set mint down on the floor and press run first mint covers the open floor area digitally mapping the room is it clean then mint spot cleans around furniture legs or other obstacles and finally move meticulously cleans edges and corners using its advanced perfect edge technology it doesn't rest until your floors are spotless and mint isn't just for dry cleaning it mops - okay so as you could see here these guys solve the slam problem in different waves so there's a small box that you put on your table or somewhere in the environment that projects an infrared pattern to the ceiling and so this is kind of turns out to be the map for the robot or the the means for localizing the robot has upwards facing infrared cameras and observe this pattern and therefore knows where it is so it actually estimates this post relative to that and once you have your post estimate mapping is easy and you see indoor what actually drive around the likes of the chairs and things like that and so that's kind of one way how they solved the actually is quite elegant way the the post estimation problem because there's no expensive set up you just need to put that box somewhere switch it on and it's an invisible pattern net you're receiving but for example I'm not sure how well it works if you have these really old buildings with really high ceiling that's questionable or if you have a robot which goes to different rooms you would have multiple of those different base stations somewhere then it may get a bit more complicated a bit more it's a suboptimal compared to having a system which could solve the same problem completely on its own but of course advantage here for those products is price and those devices are I'm not sure what the current price for this is but last year it was or two years ago it wasn't the order of 400 500 US dollars so number 300 euro so if you have devices at that price it we need to make compromises at some point we have another showcase which actually hear from Freiburg which is the Europa project that's the project we conducted here on urban navigation we had a robot was navigating the environment and that was summer last year when it made it through through from jar starting from here going to five of downtown and navigating autonomously which also required quite some mapping tasks in an orbiter of Vanda shaft in Freiburg sighing vienen from vision shaft and be delighted mostly machine a zip Standish irin fear kilometer long and big endian start fintan does clap material for phones end zone on skin and they'd say my paws a holder young gaben an Elysium nor an uncle must endeavour glider in robot ahead from farm again denim is not finished so why don't we come the I take van de Boer show kun firefight in steel soybean video bata fortune soon it's even - and chicken ok so they also other applications where this technology is used for building system that navigate autonomously through the environment and this for example one of the technology that you could imagine to work on autonomous transportation systems autonomous wheelchairs rather applications where you want to not modify the environment so you don't want to put any beatings in downtown in order to go there you want to have the system which carries also sensors move through the environment estimate where it can go knows it's pose within a map and in this way solve the surround problem which allows it to autonomously navigate so navigation was kind of the key objective here but in order to solve the navigation problem we actually needed to build accurate maps of the environment this is another short example here one of the mapping systems mapping our campus here so that's a close W this is the robot and this is kind of the proximity sensor and which give gives a distance to the closest obstacle so the Roberts driving around here so you may start realizing what you see here this is building 79 this is the men's are building this is where the s pan goes we are sitting in this building over here that's the Dutch crude alley and so you see the robot moving through the environment sometimes you see that map shaking a little bit that's one of the post Corrections that are conducted and so you can see why the robot is moving through the environment you can actually see the structure of those buildings and this information is sufficient for example for robot to localize and navigate on campus here you may observe that the robot hasn't seen everything so they are kind of white spots down here and there are other areas where part of the building structure is missing that's just the reason for that is that this is kind of a passive process so someone drive the robot around the robot records the map but the slam system itself doesn't tell the road where should go to collect the information therefore you have missing information like down here in that area but that's kind of the typical result of social slime algorithms okay so let's dive a little bit deeper into that what is typically what do we have what do we want what we have is we have a sequence of control commands which tells me what are the commands I give to gave to the robot this is what we call you want to UT so UT can be the command like drive one meter forward or stop immediately or turn twenty degree to your left hand side these are commands that are sent to the robot for example why aren't person operating the robot with a joystick or why an autonomous planning system whatever they are controls or what tries to execute these controls and these are specified by u 1 to u T so whenever you see a u in this course it means that the control or sometimes we use or we use actually controls and audiometry information actually the same thing difference is the control command is actually something which is which you physically sent to the robot so like drive a meter forward odometry is something which and when the if the robot counts the revolution of its wheels to estimate how far has it gone and reports us back this is something which we call a dama tree so it's already the first feedback from the system what it did so I may say the robot go one meter forward and the robot drives and stops and only drove 99 centimeters forward odometry may tell me you drove 99 centimeters although the command was 1 meter so it's kind of it's already out so actually it's already using sensor information which is typically some encoder which count the revolution of the wheels and we typically use this as the command because it's more accurate and be more let's get that for free from those platforms but theory it would be sufficient to just take the commands that are sent to the robot the second thing which is very important for us our observations that typically always called Z or Z 1 to T so these are this 1 2 T means at different points in time so if I write it like this once needs once to T so it means observation 1 observation 2 of the vision 3 until observation T so just different observations these observations can be laser scans so a single laser scan which tells me the proximity to the closest obstacle it can be a camera image whatever my robot has in terms of sensing capabilities so these are my observations and what we so this is given we have assumed to have that what we want to do with that we want to estimate a map of the environment so what are the environment looks like and the path of the robot note that the path has typically one index more so from X 0 to T whereas the commands go from 1 to T the reason is if I have a sequence of let's say 3 pulses between those three posts that can only execute two commands from go from 0 to 1 from 1 to 2 and therefore I typically have always one pulls more that I have control commands this please you can have but you typically the reason why we typically doesn't do that is that you use X 0 to find define the center of your referee coordinate system and then you start estimating this one that's kind of leave Y you technically don't do that but in theory you could also get an observation at the first point in time that's absolutely right quite often this X 0 is just used to kind of fix a coordinate frame and then you start the estimation process with X 1 but it's kind of more technical detail or something which has kind of typically used in in the community to do it in that way but in theory oh you're absolutely right you could do that any further question at that point in time ok one important thing to note is these quantities here they are not free of errors they contain errors this can be observation noise this can be completely bad data associations this data is not free of errors therefore we typically use probabilistic approaches to address slam problems same holds for mapping and for localization most of these techniques at least the robots and successful ones most of them use probabilistic techniques so to illustrate what that means using a probabilistic technique you can describe that by the difference between robot is exactly here - the robot is somewhere over here it's simply wrong to assume that you know where the robot is perfectly even say ok robot is here I start on the robot and everything I do I do relative to the reference frame where the robot is right now so the robot starts at 0 0 0 X 0 y 0 orientation 0 but if I say the robot go media forward or what drives the media forward even if I have a extremely accurate motion execution system the robot may not be at 1 meter x equals 1 meet about it 99.99999 centimeters so there's no what I want to illustrate is that there's no way for us to tell that there will exactly executed what we told him we may argue that if the error is extremely small we can actually neglect the uncertainty which is true so this uncertainty so this would be a sketch of a Gaussian distribution if the uncertain he approaches zero and I just get an extremely peak distribution I may be completely happy with ignoring probabilities and just assuming I perfectly know where I am but in most real-world situations this is not the case so we typically have an arrow which is non neglected ball and typically the error even accumulates over time so if I then create go another meter forward another meter forward another meter forward the error actually accumulating it's larger and larger and larger therefore at least at some point in time we need to take into account probabilistic approaches to appropriately model this uncertainty and maybe take this uncertainty into account so if you consider the example of an extremely long corridor is a narrow doorway at the end you start the robot in the middle of the corridor so what drive through the environment it completely ignores its observation because it has the perfect or close to perfect motion estimation system by just counting the revolution of the wheels at some point in time it will make a small error to the right and left-hand side at some point I'm it's super tiny but Etta quarters very long I mean may not pass through the door at the end of the corridor will smash into the wall and if you say but I'm still super super accurate I'll just say I just make the corridor ten times longer 100 times longer 1000 times longer some point in time you will he will actually collapse and the same with these probabilistic techniques and uncertainty it may be the case that your sensor or your motion execution system is so accurate that you can ignore that ignore the uncertainty but if you scale up your problem at some point in time you typically run into problems again and that's a reason why we use these probabilistic approaches for most of the techniques we do a here in robotics are not only for mapping and localization but for most of the real world problems in robotics that we do we use these probabilistic techniques because they're just very very great tools to reason about uncertainty they come at a price because modeling that is to believe very challenging and computationally very expensive and the monotony often has to make simplifying assumptions like the error is distributed according to a Gaussian distribution or something like that but nevertheless it's better than saying there's no error i perfectly know where what the world looks like ok so what does it mean in the probabilistic world we said we want to solve the slam problem we want to estimate the path of the robot and what the environment looks like so we can specify this in that way so we have this P off which is probability distribution then we have this X 0 to T which is the path of the robot through the environment its trajectory it's going to fit the the pose of the robot at discrete points in time and then we also have the map that we want to know about then we have this strange vertical bar over here which means given so we want to estimate the stuff which is here written in the front given that we know what's written here behind that that that vertical line what we have here we have our observations and we have our control commands or our odometry information and the whole thing we're going to do in this course is just how can we actually estimate that probability distribution that's kind of if you if I should present the course in one slide that's actually what we're going to do we're using different techniques to in order to get a hopefully good estimate but where the robot is and what the world looks like and the choice of the technique that we use depends on the assumptions that we can make if we can make assumptions let say we have distinct line marks in the environment we have certain sending probabilities like the sender which has a gaussian arrow there's certain estimation techniques which are well suited to solve that problem if we say we have we don't have light marks we just want to build a dense model of the environment so really represent all the physical surfaces for example the scene we may use something else or if we say we have really really weird sending Tenzing properties like this it's not at all gaussian at some other weird multimodal distribution then other estimation techniques should be used in order to get a good estimate so all these estimation techniques make assumptions and some may be more restrictive in their assumptions but then let's say easier to implement more efficient to execute it's kind of an advantage if I can assume that these assumptions hold for the technique that I'm investigating where I may relax some assumptions this may get computationally more expensive and but that has kind of the choice of the designer we will look into three different paradigms here one is a common filter and family which is made for Gaussian distributions with particle filter based techniques which can have multimodal distributions and we have graph based approaches which often assume gaussians as well but can relax it to a certain degree in better tables outliers they're computationally sometimes more demanding but have some other properties that they are more flexible how they can be used and can combine different sensing methodologies we look into these three different paradigms here and investigate them okay so we said we want to estimate this guy over here so this is something that we also call the full slam problem and if you draw that as a graphical model it looks like this so who of you has seen graphical models okay so bit more than half of that okay so briefly explain what it is so what do you see here you see these circles and you see variable names in this real circles and those variable names are we have seen before so these are observations these are controls these are the positions of the robot this is a map of the environment and these errors M represent dependencies between those variables and you can actually read these errors as influences that's the easiest interpretation say an error means it influences so for example if I'm interested in estimating the current pose XT of the robot I look to the variable XT minus 1 that is the position at the previous point in time and there's an error from XT minus 1 to XT and I can read that as XT minus 1 influences XT which makes absolutely sense if I know where I am right now or I have a pretty good estimate where I will be at the next point in time given that account out whatever travel at light speed somewhere else so read those arrows as influences we can say for example here we have the previous pose and the odometry command execute executed both influence the new position so if I know where it was and know which command are executed I have a pretty good means to estimate where I am so give my I've started here and say go one meter forward one meter forward some somewhere around this with a quite high likelihood I'm not perfectly there but I'm somewhere nearby and this can be expressed by this XT minus 1 error 2 XT and an arrow from UT minus 1 to UT if you look to the observations what we're going to observe depends so for example the landmark or the the position of the whiteboard here it depends what the world looks like so where it's a whiteboard in space and it depends on where I am if I'm here and observe the whiteboard we would say okay it's a meter to my right hand side if I'm standing over here will be 2 meters to my right-hand side so it first depends where's the whiteboard in the environment and where is the sensor and if I have these two information I can probably get a good estimate of what I'm going to measure and this please yeah or what the environment the environment you can even see that at the environment you can also see if you see this as landmarks let's say distinct landmarks is where are those landmarks in the world so it so it depends on yes it's a good question so the thing is the important thing is what the world looks like but given that I build a map this map should tell me something what the world looks like so the the estimate so the my estimated map also tells me something about what I'm going to observe but in general you're right what I'm interested in is the environment itself ok and we have those variables which are here which have this this dark grey background over here that means these are the variables we want to estimate so these are our unknowns and the other variables these grey variables here are our knowns so these are the unknown quantities and these are the observed quantities and these graphical models so we won't use them very often this course they are kind of a nice way for illustrating dependencies and also assumptions independence assumptions that we make because if you have an arrow from here to here it means if you want to estimate X the XT we should take into account on those variables which have an arrow pointing to that variable because it means they are influenced by so XT is influenced by XT minus one so if I know XT minus 1 I get a better estimate of XT and if I kind of drop an arrow somewhere can quite nicely illustrate modeling assumptions with that course I can assume it's just a model I create I can assume that are the current poles of the robot doesn't depend on the previous post that's just my model of the world if I make this assumptions assumption it's quite likely that my estimate gets worse but I can do that and these graphical models are kind of nice to illustrate those independence assumptions and this is what we call full slam so when I estimate the full trajectory of the robot and we want to estimate what the environment looks like sometimes one is not interested in full slam we're estimate the full path of the robot but I'm interested what we call online slam I just want to estimate the current pose of the robot and the map build up to the current point in time that's what's written he has a small T so it's not necessarily the whole sequence or small T is within 0 and and large team so I want to estimate we have the robot currently and what are the environment currently looked like give them all my previous sensor data that's actually something that most robots will use if they want to make decisions based on where they are where they want to go if I'm not interested we have been in the past given up a map of the environment I just want to know where I am right now so for most real-world applications this online slam is actually the interesting property I don't want to collect all the sensor information beforehand and then build a map and estimate where the robot was I want to do it online right now ok if you write that as a graphical model if exactly the same structure over here but we typically only have the great aerial variables so those variables that you want to estimate is only these the last post and the previous ones are not interesting for me anymore from mathematical point of view this means we need to integrate out all the previous pulses so the only interested in estimating the position at time T and the map of the environment this is actually an integral over all the possible locations at x0 all the possible rotation x1 x2 x3 until XT minus 1 of the full slam posterior right if I integrate out the variables I kind of removed them from my estimate so this is a full slam posterior here's X 0 to X T and if I integrate out X 0 to X C minus 1 I actually get the probability distribution which is the the variable XT just occurred point time this holds for all variables so if I have a probability a joint probability distribution P a and B so just to whatever quantities of an estimate I can actually say P of a is the integral over all possible B's ok or let's say let's write it informally I integrate over all B's of P of a and B DB and so what remains if I integrate about all possible outcomes that B can take I end up having the probability distribution body this is exactly the same thing I do here so there's no like magic in there it's just the integral of all those positions and how these integrals are soft is kind of recursively one at a time so if I go from XT if I go from X 0 to X 1 I do that estimator step and get rid of X 0 and then next point in time I move the word move from X 1 to X 2 it multiply X 1 to X 2 and then integrates rx 111 in successive iterative process while the robot move to the environment so at every point in time one of those integrals is solved ok so that's kind of our graphical model for online slime and the corresponding distribution down here and different techniques we will see in this course offer online slam problem or the full slam problem all very end of that and just depends on what my problem with which M technique I'm going to apply to solve that okay so one motivation just to say why is slime actually a difficult problem the first thing in reality is what we have is that the the estimate of the past posterior in the estimate of the met posterior they actually correlated they are they're both unknown they're both correlated so we don't know the past we don't know what the environment looks like want to estimate both and at the same time those estimates are correlated so they depend on each other ok we have an example here so that's a robot drive through the environment measures those two sorts to networks moves on so in this the circle should represent actually the the uncertainty it has about the position of those landmarks so it doesn't know anything this is other the true locations of those landmarks and so it estimates these guys over here this guy sits over there and then the robot moves on while it moves on it ends on being here but it doesn't really know where it is so it hasn't kind of a mean estimate in an uncertainty for example in here so you can see that here the uncertainty was basically zero just started off the robot it said ok I start at zero zero zero let's send off my reference frame here I go perfectly nowhere M now I go five meters forward and it on really no if I went five meters forward maybe for me 250 maybe 5v 250 maybe a little bit to the right or to the left hand side and therefore I have this uncertainty over here so motion increases the uncertainty of the system right okay okay then again the robot measures these two landmarks and you can see here also we used exactly the same sensor reading same sensor and so the uncertainty is around this line mark and this landmark should actually be the same than this line mark over here but the the reason why they are bigger is that I need to combine the uncertainty the robot has where did the observation and the motions are the observation uncertainty and therefore these ellipses are bigger because I still have some uncertainty because I didn't really know where I was plus the uncertainty of my sensor reading and the robot again the robot continues moves forward and now happens one thing it actually observes reabsorbs the landmark and by reabsorbing a landmark and say okay I get already a better estimate for M because now they it has an expectation of what it should measure given the model you can say okay I measure something else so I actually can also correct the map a little bit and this is shown by this small black circles over here so this is the M this is the uncertainty ellipse after the the next update step the renderable updates its map because has reabsorbed something so it gains more information they can see also it was just observing this landmark over here and if it gets more certain about the location of this landmark over here it will automatically get more certain about where it has been before because if I know the position of this guy better that will also reduce the uncertainty of this estimate because I made an observation from here to that landmark beforehand and so all the map estimate the position of the landmarks in this case and the estimate about the poses that the robot has been they are actually correlated so if I gain information about one part this impacts all the other and so given that there is a dependency that I cannot estimate them separately I cannot say I only estimate the posters and then solve the mapping problem that's something which typically doesn't work because you neglect the dependencies in here the second thing why flam is a different difficult problem is data Association so if I the sensor observes something I need to actually relate what I see it what I've seen before so for example if I go back to this example exactly in this situation so next one here the wrote now makes a new perception and this okay what I've seen here is exactly the letter saying that mark I've seen before this situation may be easy because they're not many landmarks but assume that here are 10 landmarks really close close together nearby it's quite likely that you kind of flipped the Association depending on how distinct those landmarks are these are all identically looking poles or trees making data Association errors is quite likely but if they are let's say have a very good feature description that may not happen that often but in practice it happens from time to time that robot confuses two places or two landmarks and the other thing is that also the uncertainty of the towles estimate impacts the data Association so let's say this is my uncertainty at the moment and I get an observation which is kind of I see these two features these green dots so I can either be here sitting here on the left or I can be sitting on the right and in okay this situation is especially constructed to illustrate that both have exactly the same likelihood so just because I have motion uncertainty or uncertainty in my current pulse estimate that makes a decision hotter and the other thing is that picking the wrong daily Association here actually leads to a wrong estimate because if I say ok this is the right data Association so I know I can't be here so this uncertainty really gets smaller and the mean will shift towards this this position if on the other hand on the other hand say this was the right thing then the position of the robot moves more to the right hand side over here and so then I get this observation if I assume that this observation is right and so in this situation this would be the uncertainty of the robot probably and in this situation that would be the uncertainty of the robot and so the uncertainty gets smaller and if I did the wrong Association I get a wrong estimate of my uncertainty and that's something I don't want of course I can't get it to really get overly confident of where I am which is and this something which is not true so I get an inconsistent estimate that's kind of reasons why slam is a non-trivial problem I have this dependencies between those variables and also this data cessation errors is there two things why it is still a tricky problem at that point in time are there any questions ok so then we would like to go quickly through a typical taxonomy of slam Ivor's and so how can you describe different slam Agra's and what makes it indistinct the first thing is on kind of what kind of Maps do they estimate we have one class of approaches which generates volumetric representations so like for example if you see this over here that's actually building 52 and 51 on our campus built with Robert was standing here having a pencil 3d a pentile laser scanner and building a map of the environment so I get really this these physical structure of all the surfaces of all the points that I can observe or um there's also something you will see quite often this course this is typical 2d map white means free space black means occupied space and gray means I don't know or wood has never seen that part so this is like an architectural floor plan but just adding all the furniture and all the stuff which lies around in there in the apartment or in the building and so this is also a volumetric representation in 2d so you have the free space over here any of the the black points which are obstacle locations in contrast of that you may have feature based approaches which do not attempt to model all the objects in the environment but they just represent to represent distinct landmarks this example here this is the Victoria Park a University of Sydney in Australia and it's one of the kind of a very famous data said they recorded a lot of time ago and they had trees over here and they had a laser scanner and was just estimating circular things it was a trying seem to be the trunk of the tree and every tree trunk created feature so just drive around just want to estimate the position of those features if you know where all the trees are you can even localize the road with this feature based approach the advantage of this feature based approach is they'd still be a very compact representation I just need to store the position of those trees it's kind of really nice from a Robotics perspective on the other hand it requires to have means to assay this feature I see here is exactly this tree there which is often hard to do for depending on your feature depending on your sensor may be hard to do and these are kind of the disadvantages of those feature based approaches there's always a pro nakhon for both sides if you are happy on localising you just want to if you have some distinct landmarks feature base is a nice approach if you don't know what you're going to expect or you really want all the obstacles in the environment because you want to navigate with that need to obstacle avoidance let's approach may be better depends on your application on your estimation technique the thing that people often differentiate are topological approaches versus geometric approaches one situation you try to estimate really the geometry so this is kind of a typical map you can you can you can buy or get somewhere so these are the streets that's not what Google Maps is kind of the old-style maps look like that both of you haven't never seen them so these were the streets either the buildings so this is a typical geometrical representation of the environment what you see here is a subway map and of Paris I guess yeah first and what you see here only are the connections between places and even the position of those places maybe not exactly at their geometric location so the distance between those two places may be dramatically different than the distance between those two places this justice describes you how argue I get from A to B using the subway and for solving subway navigation that's much more convenient than representing the subway in a geometrical way because you don't care where the subway train goes exactly just one know if I bought whatever train number eight I get to that station so depending on the application you're trying to solve topological representations may be better than geometric representations as well as the other way around again topological maps are very compact you can describe them in a nice graph you can use standard planning algorithms like a star which operate on graphs so using these topological representations can be advantages nevertheless most approaches use geometric approaches so topological approaches were pretty popular ten years ago something like that there are some people who try to again re-establish topological approaches as some nice properties they have some nice properties I want to say the difference here something else here but for most robotic applications geometric models are the models that are choosing it that people use other things is known vs. unknown correspondences so that's a slam algorithm that I develop assume to have perfect data Association there was the example we had before so if I get this observation do I know that is where these two landmarks or things simply no idea some some approaches make the Explorer most approaches actually assume to have perfect data Association we see a feature you know which feature it is that's unrealistic but it's pretty hard to track all possible data sensations there's a number of possible data set data Association explodes quite quickly they are however approach to say ok I assume to have a certain number of outliers or wrong data associations in in my incoming data and I try to deal with that so it's just something in differentiate the earthing is what you often find is static versus dynamic environments it's the environment not changing so it's the same so this our robot driving over campus no one around I mean the plants are growing over time but we can say that's a very very small change I ignore that but if you're driving with people in your surrounding and the scene looks like this that's highly dynamic things change it's partially hard to recognize that you're the same place just be there are so many dynamic obstacles around so there are approaches which explicitly say we want to get rid of the static world assumption and really want to allow to model dynamics or changing worlds and that's a much more challenging problem than making the static world assumption which most approaches to what can also differentiate approaches is the ability to represent uncertainty sometimes approaches at least the way they are used assumed to have small uncertainty in the post estimate so cannot handle dramatic errors of the pose estimate so the root says okay I'm quite likely to be somewhere over here versus I can be here somewhere over here or here or here or here or here or here here just a number of different hypotheses the system can maintain or the way the uncertainty is represented for example if I have a Gaussian distribution I can simply increase my variance and I get a bigger uncertainty without making the representation itself more complex if you use other ways for representing uncertainty like sample based representations you may need much more samples to actually represent uncertainty explicit better so that's kind of a difference what also distinguished approaches is active versus passive slam so we will look mainly into passive slam here that means we assume the robot is controlled by someone else by some person by some algorithm we don't care we just say here the incoming data stream and we work on that incoming data stream let's standard slam which is passive there are other approaches towards active slam but the robot needs to should make its own decisions of where to go in order to build a good map of the environment that then kind of involves also local exploration or go to explore the environment or should decide where to go to get better maps let's also sometimes referred to as active slam we will mainly look at the passive slam so you can assume that someone dies or over the wrong with the joystick the next thing we see is sometimes M any time or any space slam algorithm that means I just have a certain amount of time available let's say whatever 20 milliseconds per observation that I'm allowed to spend on my estimation system I don't have more resources do the best you can with this 20 milliseconds or so I'm saying okay the robot has only one kilobyte of RAM which it can donate to its map estimate but so this is not sufficient to represent the whole environment what should the robot forget and what should the robot focus on and if I increase this memory how does it change so these are kind of any space algorithms whatever constraints I gave so the more memory I have the better the more time I have the better but what can I do with a certain amount of computational resources or certain amount of memory that's also something you often find and then you have kind of single robot systems versus multi robot systems so you have a single robot which does fly them wherever multiple robots because if you have multiple robots they need to also make data associations among the platform's they can be more tricky but with more modern approaches with this graph based approaches this problem is actually not that dramatic anymore so it can be integrated nicely into the same framework and doesn't require some extra handling as it was the case before so you don't find this distinction single robot multi robot slammed that often anymore as it was done in let's say five to ten years ago okay so we have a large number of different properties of those slam algorithm of those slam systems or requirements that we need to address and there are a large number of different algorithms that we can use to solve the same problem they all have certain advantages in certain settings under certain assumption this is the optimal approach on other other assumptions this is the best approximation that I can do where I can compute in a certain amount of time so this large number of approaches out there and still a large number of solutions are proposed these days so if you go to a center robotics conference you find multiple tracks actually associated to slime problems or slime related problems and there's also a big interest from commercial users these days which try to build robots or robotic devices devices using robotics technology to model the environment to estimate the other device actually is most of these approaches use probabilistic techniques they are very very few which ignore that in there typically it took very efficient but not met break in performance and therefore there's no way around probabilistic techniques in context of land problems these days this story in slam at least in robotics goes back to let's say the mid 80s when people started to investigate that but it should be noted that there are other fields where similar problems have been addressed years ago so if you look to geodesy people are measuring the earth measuring the size of countries where light marks they faced very similar problems whatever the end of the eighteen hundred's century something like this you have very interesting problems which arose years ago and people used message which are still very related to what we are doing here today we may have different requirements with robots and let's say some problems that they have these days so cavitation time was breathing issue 200-300 years ago everything had to be done by hand so that other problems like calculation errors which became kind of ignore today and some of the focus was maybe let some somewhat different but still they use or address very similar problems and if we go back at least to a slam history in robotics so it started in 85 86 with miss and his team as well as your own right started to describe or use concepts to describe the uncertainty in geometric relations between observations between landmarks and then they have been discovered that Accra which is the biggest robotics conference so definitely Conference on robotics and automation on how to sell this land problem and then followed by one of the kind of seminal or key papers by Smith south and Cheeseman in the beginning of the 90s the common filter based approaches became popular this one estimation technique developed in around 1950 the Kalman filter which is frequently used in robotics and then actually the acronym slam was gone and is art in a workshop ideas are 95 you sometimes timed also CML for concurrent mapping and localization but slam simply sounds better than CML and therefore people stick to the slam and then the very first concert convergence proofs in the late 90s so that they can show under certain conditions the system will actually converge to the right solution under certain assumptions and the first reload system that we're operating with those techniques and 2000 on wide interest started sore knee approaches were published going beyond common filters using particle filter based approaches and also the graph basic approach became more popular so in this course we will look into the three main paradigms Kalman filter approaches particle based approaches and graph based approaches and in order to do that we can have a look to our graphical model and all those approaches use two concepts the first one is a a mock so-called motion model and the second thing is the so-called observation model the motion model tells me how that the robot move and the observation models how should I interpret my observation and the motion model is actually this part over here in the graphical model so how do i estimate XT given I know XT minus 1 and UT so this this estimation process over here is what we call the motion model so how do I get this guy given this one in this one and the observation model it says what's the likelihood of an observation given I know where the robot is and given I know what the what the world looks like so motion model tells me what the distribution about the new pose of the robot given I know the old poor-poor pose sorry and the control of the Adamo tree command so given I know I was here given us a go meter forward what the probability distribution of where I end up that's the motion model so if you have a Gaussian motion model this may be initial distribution if you move forward let's say go media forward you end up maybe with this distribution if you have a non Gaussian model that means you don't have a Gaussian distribution from other means of distribution so what starts here goes here and then this may be what so called a banana shaped distribution so it looks like kind of a banana and the the the angular so this in this kind of banana shape actually results from the orientation that the robot has and the nonlinear dependency between the state and the and the angular component or if you put in a sample based representation that's also a form of banana-shaped distribution we have a standard odometry model that means the robot is at one point X Y theta and should end up at X prime Y prime Sita Prime how can we go there we can express every motion in the plane by one rotation the translation and the second rotation can describe a transformation between two poses easily so if this is the current pole so this is the heading of the robotic first rotate here then move straight here and then rotate here so with three components I can express this now these are the equations you can do that so that's just kind of the Euclidean distance between those two poses this is the arca stands for this transformation and then just a subtraction of the angular components that was something that we looked into in more detail in the robotics one course how to express this and so there's we are recording from from this year that's chapter number six we can look that up again we French that while you look into the probably see robotics book in Chapter five which tells you something about the motion model so if you're unaware of that I recommend you to take the book read that chapter it's not that difficult to understand and kind of refresh that we will I will talk a little bit about that next week as well give you again a reminder but it may be go to have read that the second thing is the observation model this is kind of distribution about what I'm going to observe given I know the pose or not the state also given though the map which is maybe neglect here which tells you a kind of how do I relay so what I'm going to expect to measure given I know what the boat looks like so in the Gaussian world let's say I'm here I know that the length mark is here so this is my probability distribution that I'm going to expect so if I'm standing here I'm facing the wall I measure the distance to the wall I measure something like whatever 5 meters plus minus a little bit or if ever non-gaussian models you may get other the beginning rather weird-looking distribution so that's for laser range scanner modeling certain aspects such as dynamics above the scene again chapter number seven in the robotics course or chapter number six in the probably seek robotics school book skim over it refresh your mind again I will talk about that next week as well but just for you - let's say pre pure a little bit for next week that's something I would recommend okay so time to sum up is that mapping is a task of modeling the environment localization is a task of estimating the pose of the robot in the environment in insulin we want to do both things at the same point in time so simultaneous localization and mapping that what the name actually tells us we've seen first full slam opposed to online slam so you should understood today what are the structural differences between both once I'm estimating the whole trajectory once only the last post or the current post and also kind of roughly introduced a taxonomy of the slam problems like what are typical things you distinguish between that I try to do a last slide for every course here and giving you a kind of literature way you can actually read really that these topics or read it again where you find more details so the overview you find the handbook on robotics and step turn simultaneous localization and mapping subsections 1 & 2 other things we covered here today so you can can read that there and on motion and observation models I just had one slide for that and all that's very short it's a probabilistic robotics chapter 5 & 6 & 6 & 7 you find that of 5 & 6 in the progressive robotics book and 6 & 7 in the rope in the robotics course where there also video recordings from last year so if you want to know more about that read through that although I will talk about these models in the context of the base for the next week as well that's it from my side are there any questions from your side

Channel: Cyrill Stachniss

Views: 267,834

Rating: 4.9706602 out of 5

Keywords: robotics, Simultaneous Localization And Mapping, Robotic Mapping

Id: wVsfCnyt5jA

Length: 76min 35sec (4595 seconds)

Published: Mon Oct 21 2013