Go Down

Topic: Simple (?) SLAM created map (Read 2563 times) previous topic - next topic

grint

It's well documented that creating a 3D map using SLAM is relatively difficult in a garden giving the potential lack of distinguishing features.

My idea is to put high visibility stickers in obvious locations, not many - maybe as few as 5, that can provide a reference point for a robot for the mapping process - they can come down again after the mapping is complete. The ONLY data I wish to capture is what the robot is moving over: is it grass, a path, is there a dropoff point, is there an obstacle, is the robot in a lower or higher part of the garden. The robot would have all of these sensors on board so that isn't really the question.

The questions I have are:
- could a very few reference points be used to create such a map?
- what laser system could be used given that it's only looking for a very few reference points?
- how much processing power is this likely to take?

Your help is appreciated...

grint

PaulS

Quote
they can come down again after the mapping is complete.

What is the purpose of creating the map? A map is useless if it is not used. A map is useless if you don't have a frame of reference.

So, taking the markers down after the creating the map means that the map is going to be useless. So, why bother?

Quote
- could a very few reference points be used to create such a map?

As few as 4 could be used. All that they do is define a coordinate system. Assuming, of course, that the robot knows where it is with respect to that coordinate system - an assumption that is rarely valid.

Quote
- what laser system could be used given that it's only looking for a very few reference points?

The number of markers has no bearing on the suitability of a particular sensor system.

Quote
- how much processing power is this likely to take?

Twentyseven gigacycles per millennium. You've given no clue as to what "this" means, or how long you are willing to wait for the map to be complete, so no reasonable answer is possible.

Processing power is rarely the issue with SLAM. Memory is. As is knowing where you are.
The art of getting good answers lies in asking good questions.

grint

- The purpose of defining a map whilst the stickers are up is so that fixed points on the map are identifiable to the robot when it encounters them after the stickers come down e.g. a tree, or a swing. This will help the robot with localisation issues and help remove errors of spatial awareness. There might be 100 fixed points that would be incorporated into the map under the umbrella view of the stickers i.e. this could be done without the stickers, but the stickers and a reference to them would reduce the error rate in establishing the map and its boundaries.

The use of the map would be for a robot to mow the lawn, or drive a set course around the lawn or other use where a more clearly predictable path would be needed.

- What type of sensor system would be useful in this situation?

- How much memory would be needed to do this on the fly as the robot was moving around?


PaulS

Quote
- The purpose of defining a map whilst the stickers are up is so that fixed points on the map are identifiable to the robot when it encounters them after the stickers come down e.g. a tree, or a swing. This will help the robot with localisation issues and help remove errors of spatial awareness. There might be 100 fixed points that would be incorporated into the map under the umbrella view of the stickers i.e. this could be done without the stickers, but the stickers and a reference to them would reduce the error rate in establishing the map and its boundaries.

So, what happens when the robot goes to mow the grass, and has no idea where it is on the map?

Quote
- What type of sensor system would be useful in this situation?

An awful lot depends on the size of the area to be mapped, how the Arduino will move the sensors, if that is needed, how fast the robot is moving, and many other details that I must have missed. What are you intending to sense? Trees? Stairs? People?

Quote
- How much memory would be needed to do this on the fly as the robot was moving around?

How fine is the map to be? 5 cm cubes for a 25 x 25 kilometer field? Or 25 kilometer cubes for a 5 meter square field?
The art of getting good answers lies in asking good questions.

grint

The robot starts at a base so knows its (0,0) position. When the preliminary map is completed the robot will know the location of quite a few numbered markers. I'm thinking these could be sub-soil so a sensor would need to be able to sense them through a few centimetres of dirt. There could also be a perimeter wire to define the outer boundary.

If it would help to clarify the problem think of trying to mow lane-by-lane. If there was a perimeter wire and a sequence of numbered pegs around the edge then a pure lane-by-lane would be possible as the robot would know when it hit a perimeter wire and found a peg exactly where it was and if its internal calculations were off, it could recalibrate on the fly.

All of that depends on it having an accurate map to start with, hence the stickers and spacial construction process.

10 cm cubes would be about right though possibly as small as 5cm2 Lawn sizes up to 2000m2

PaulS

Quote
When the preliminary map is completed the robot will know the location of quite a few numbered markers.

Relative to what?

Quote
The robot starts at a base so knows its (0,0) position.

That says nothing about its coordinate system, other than its origin.

Quote
All of that depends on it having an accurate map to start with, hence the stickers and spacial construction process.

Where are you going to store this map? If it's in PROGMEM, how will you get the data to store there? EEPROM (internal, anyway) is too small.

Quote
10 cm cubes would be about right though possibly as small as 5cm2 Lawn sizes up to 2000m2

So, at a minimum, a 1 x 20,000 x 20,000 array. There isn't an Arduino around that can store 400,000,000 bytes of data. Forget the smaller grid. And forget about 3D.
The art of getting good answers lies in asking good questions.

keeper63

I'm not sure that grint understands the basic concepts of SLAM. I'm not going to claim to be an expert; my only experience with SLAM comes from what I have read, and what I learned via the Udacity 373 course (back in 2012 - so I am a bit rusty).

SLAM is - at it's core - a methodology to provide mapping and localization of a (generally) robotic platform in order for that robot to be able to determine it's location at a future time - to within a certain level of probability.

The basic algorithm is a measure-move-measure sequence - where the "measurement" is whatever data the robot gets from a localization sensor - which could be any number of things, but generally is some form of Lidar sensor, or ultrasonics - but it doesn't have to be; ultimately, it just needs to be some form of a sensing system to give the robot some kind of information about the environment it could use to determine location.

So - it measures and stores the data - then it moves in some direction - then it measures again. It then tries to get a probability about the second measurement in relation to the first - how probable - that is what percentage of chance - is there that where it moved matches some previously known sensor data? Now - of course at first nearly every measurement the robot makes will have a probability of matching of zero, or very close to zero. But over time, as more and more measurements (and movements) are made - the robot will be able to compare a measurement to its internal map, and come up with a probability that is greater than 50 percent, and ultimately closer to 100 percent. It will likely never have 100 percent certainty; noise in the sensors, slipping motors, a constantly changing environment (especially with an outdoor robot!) - will all conspire to ensure that the robot will never be 100 percent certain, but it will likely be 98 percent certain - depending on the algorithm employed and the amount of training on the environment of course.

So - what sensors could be used, then? Well - I've already mentioned Lidar and ultrasonic sensors. Both of those are actually really good to work with. You could also have outbound fiducial (or other) sensors - that sense where the robot is and relay it back to the robot (or the robot looks for the fixed sensors - in some manner - in order to localize - which seems similar to what grint wants to do). Vision sensors could also be used - basically sense the location within the environment by sensing the shapes, shadows, light, color, etc - of the environment, and making the guesses.

Any one of these (and many more) could be made to work - but in reality, you want as many of them as possible, then combine the data from all the sensors into your map; because none of the sensors will be accurate in all situations, but some will be more accurate than others in certain situations, getting multiple data points from multiple sensors for each measure will be better in the long run and likely would increase the probability levels (for example, a Lidar could detect a sound porous surface an ultrasonic sensor might miss - on the other hand, an ultrasonic sensor may well give better data than the Lidar in other situations).

But you have constraints (budget and otherwise) for a lawnmowing robot. You want something robust, easy to deploy and use. Here's a proposal:

Imagine setting up "lawn spikes" of plastic (or other non-ferrous and sturdy material - plastic is cheap, though) with a small rare-earth magnet attached to the "head". Plastic golf tees with a small disk magnet attached would be perfect. Now - place these around on the lawn in a distinctly non-deterministic manner (the closer to random you can get, the better). You want to space them about 5-10 cm apart or so, maybe more - experimentation will be your best guide.

Also - add your RF perimeter wire as well. The robot will be able to sense this edge. The robot should also have bump sensors (or some other kind of proximity sensors) to determine other obstacles. Finally, put on the bottom of the robot several hall-effect sensors in a pattern (the more the better!) - which the robot can use to sense the magnets on the lawn.

By the pattern of the magnets sensings, combined with the sensing of the perimeter wire, along with the sensing of any bump/proximity sensors - all of this information should be enough for the robot to determine its position and orientation via a SLAM algorithm. Using magnets on the lawn will reduce maintenance (and indeed, you could even do the perimeter in magnets as well) - no need to worry about supplying power, they'll also be mostly invisible (aesthetics) if pressed flush with the ground.

You won't be able to do the SLAM processing, though, with an Arduino. You'll want at a minimum some kind of powerful single board computer - a Raspberry Pi or something similar would be a good place to start; ideally, you want something that can have a lot of on-board memory to store and process the map quickly, as well as a fast enough CPU to churn through the data and generate the probability of the location, given the sensor data sensed in relation to what has been learned in the past about the environment.

Adding other sensors to the robot might be useful - maybe a vision sensor (a web camera - to sense color of grass, buildings, edging, etc?) - maybe some ultrasonic sensors (to determine rough distances to obstacles). Some form of Lidar would be great, but there aren't many low-cost systems out there suitable for outdoor usage (that said, it seems that SICK LMS-29x devices are appearing on Ebay in greater numbers recently; I managed to pick one up for about $200.00 recently, a fraction of its original new cost - a bit of work later, plus a trip to and from the manufacturer - and I had it measuring data using it's software test suite).

grint, you might want to brush up on the concepts of SLAM some more - the basic concepts, how it works with probabilities, etc. I can't tell you how valuable I found the Udacity CS373 course to be to helping me better understand SLAM, in addition to many other topics surrounding it. If you have a chunk of time (8-12 weeks or so - it's at your own pace, though - so you could go longer if you wanted), I strongly encourage you to take it. You will need to understand and be able to implement algorithms using probabilities and linear algebra - so be aware of that going in (other courses are available from Udacity and other MOOCs that can help you prepare).
I will not respond to Arduino help PM's from random forum users; if you have such a question, start a new topic thread.

filmo

SLAM (simple or otherwise) is higher on the stack than coding for Arduino.

A good place to look for useful implementations of this would be on the ROS Documentation Wiki . This link show may examples and implementations.

I doubt you're going to get any form of SLAM working just on a microcontroller.  Rather, you'll use the microcontroller to gather sensor data and/or drive the wheels of the robot and a full stack computer will implement the SLAM algorithms. In other words, the Arduino will probably only tangentially be involved in the SLAM algorithm either in a data acquisition mode or executing wheel commands.



grint

#8
Sep 23, 2014, 04:14 pm Last Edit: Sep 23, 2014, 04:17 pm by grint Reason: 1
I appreciate all of your inputs, and hearing that Arduino is probably not the way to go is helpful.

Quote
By the pattern of the magnets sensings, combined with the sensing of the perimeter wire, along with the sensing of any bump/proximity sensors - all of this information should be enough for the robot to determine its position and orientation via a SLAM algorithm.


cr0sh is spot on here: the point of adding in numbered markers around the perimeter was so that each time that robot got to the perimeter it would be able to check its measured-moved-measured position against a known object.  I may not have been clear enough about the numbered pegs usage. Setting the magnets 5-10cm apart would probably be unrealistic even in a smallish lawn - I would expect the SLAM algorithms to not take the robot much that off course in such a short time. A maximum of a 5%(?) error rate as the robot moved across the lawn would mean that on our 10m wide lawn would have at most a 50cm offtrack robot (assuming of course it was at the outer edge of positional reliability)

Magnets were not something I had considered; I was thinking more along the lines of BLE each with a unique ID though obviously powering these then needs to be built in to the solution, and adding in BLEs also adds in $s.

filmo: What would be involved in a
Quote
full stack computer
if I were building a PCB from scratch? I know the speed of computation is the critical thing so processing power, and RAM. You may not be able to answer this, but from your experience what do you think would be needed? BTW: thanks for the ROS link - I was not aware of that.  :)

keeper63


Magnets were not something I had considered; I was thinking more along the lines of BLE each with a unique ID though obviously powering these then needs to be built in to the solution, and adding in BLEs also adds in $s.


I still don't think you are understanding the point of SLAM - which is to determine where in the environment the robot is located at, within a certain level/degree of probability - by sensing patterns of sensor data from the environment and "matching" it with stored sensor data (the map), using any one of a number of algorithms.

Those environmental factors don't need to have any identifying information, nor do they need to be active. Granted, if you did make them active or add some kind of identifiers to them - it could certainly help the situation - but it isn't absolutely necessary. You could easily implement a SLAM algorithm (not a great nor accurate one, mind you) that could navigate and map using readings from touch-sensor "whiskers" on the robot platform.

There have been robotics research projects done using only ultrasonic distance sensors (generally arranged in a ring) to provide data for SLAM algorithm. For a lawnbot, I think a combination of ultrasonics, hall-effect/magnets, and bump sensors would be more than adequate. Implementation is where it will get tricky.

If I were building such a system "from scratch" and -had- to populate a custom PCB, I would go for using some kind of small SOC device from either Intel or Arm.
I will not respond to Arduino help PM's from random forum users; if you have such a question, start a new topic thread.

grint

Thanks cr0sh - I'll look in to the Intel/Arm SOC chip...

Go Up