Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Patrick, Thu Aug 08 2013, 05:02AMi need some input here. Path planning is looking scary...
im at this moment in Grand Forks North Dakota, far from California! im attending the IARC 2013 mission 6 event. I attended the formal presentation and flight events, so I have details on the flying bots, reasoning on design, and I witnessed 8 hours of the actual flight attempts.
My specific questions are:
First, many teams are using base stations of multiple laptops, and on-vehical single board computers like the intel Atom, raspberryPI, and the Odroid X/X2. typically, they use lidar -> onboard Ubuntu Linux -> Robot operating system (ROS.org stuff). so there not coding orginal source. some teams run full SLAM too on the ground station, then WiFi up the final path to the bot in real time.
Is all this necessary? or can it be made to work on an STM32F4 or a RaspberryPI (not using a full PC-like OS)? or is path planning so complicated, that you need a highly developed code, using high-power processing?
Second, its really a 2-d problem, as elevation is largely irrelevant so long as we mostly hold constant altitude. As you can see the arena is mostly orthogonal but for the bend in the hallway, does this simplify things? as opposed the a natural river or mountain that would have curves all over.
So is there a math-geometry model that could be implemented in C code for the STM32 or similar embedded board? I have a year to code and refine this potential option.
Third, my hope and preference is something like : XV-11 lidar -> STM32 (or similar) -> flight controller -> lift fans. and no base station actively involved, other than receiving telemetry and cool video.
on a related note, I often see the otherwise successful flights end with a straight flight into a wall, that previously was flown past without problem. I think what happens is with all the unique hardware and software on and off board, with wifi and ground station real time flight planning, the bots lose sync. Then the obstacle 3 seconds away generates a 5 second avoidance response, so the bot crashes then 2 seconds after total destruction the wifi message to avoid the obstacle comes through. I believe sync and latency issues become more severe more complicated computing models.
ive got pics:
a typical arena, meant to approximate an enemy office space. We students are tasked with covert window entry, then a theft of a USB flash drive with secret terrorist plans off a desk. fully autonomous flight only, no pre-programming or surveying is allowed, no human pilot of course. We are not allowed to know the location of the object, nor the layout of the office space.
a common approximation of the Georgia Tech and Michigan University's flight attempts from 2012, I personally witnessed (amazing!)
This years arena...
Georgia tech's is a capable design, and has worked better than most.
they have modified the convetional Lidar maps to nearly solve the shortening and bending issue common with lidar generated maps.
the required presentation to the IARC staff.
ABC
Avionics...
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Carbon_Rod, Thu Aug 08 2013, 06:46AM
A full SLAM implementation is not necessary for such a small map.
However, todays high-powered laptops can run fairly accurate systems that do this task.
Success is improbable if people try it on anything less than a good quad-core... ROS is a resource pig, and fundamentally flawed in other ways.
There are many types of Path planners, but simple grid-abstraction solvers like probabilistic Maze learning AIs use few resources.
Probability of success for a completely unique implementation is low, as people spent many years trying things that didn't work to find methods that do:
Carbon_Rod, Thu Aug 08 2013, 06:46AM
A full SLAM implementation is not necessary for such a small map.
However, todays high-powered laptops can run fairly accurate systems that do this task.
Success is improbable if people try it on anything less than a good quad-core... ROS is a resource pig, and fundamentally flawed in other ways.
There are many types of Path planners, but simple grid-abstraction solvers like probabilistic Maze learning AIs use few resources.
Probability of success for a completely unique implementation is low, as people spent many years trying things that didn't work to find methods that do:
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Patrick, Thu Aug 08 2013, 07:11AM
I need something better than wall following, but less demanding than a full SLAM implementation.
let me look at your link....
Patrick, Thu Aug 08 2013, 07:11AM
Carbon_Rod wrote ...
There are many types of Path planners, but simple grid-abstraction solvers like probabilistic Maze learning AIs use few resources.
Probability of success for a completely unique implementation is low, as people spent many years trying things that didn't work to find methods that do:
See, this is what I need this forum and you guys for!There are many types of Path planners, but simple grid-abstraction solvers like probabilistic Maze learning AIs use few resources.
Probability of success for a completely unique implementation is low, as people spent many years trying things that didn't work to find methods that do:
I need something better than wall following, but less demanding than a full SLAM implementation.
let me look at your link....
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Carbon_Rod, Thu Aug 08 2013, 07:31AM
As this maze has no cycles, you can solve it with a follower, and "fetch routine" override....
Carbon_Rod, Thu Aug 08 2013, 07:31AM
As this maze has no cycles, you can solve it with a follower, and "fetch routine" override....
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Patrick, Thu Aug 08 2013, 03:48PM
I see your wall following pic, and its already easier than you've drawn.
well maybe wall following is the way to go ? I do have a 45 foot max range lidar. I don't actually have to physically traverse the wall do I ? (as long as the lidar returns a definite wall and not more unexplored frontier.)
as for it being easier than you've drawn. we have several doors, some without signs, 3 with signs. "ministry of torture", 'security chief" and one other, and were guaranteed that the goal object is in the security chief's office. ive been able to read all of the signs already with a special device I have using OCR. so I think I would only need to wall follow the hallway and one room. this pic is of this years challenge.
pic:
if I can read the signs I don't need to search more than the hallway or at worst 2 rooms deep.
does the bot have to physically follow the wall?
using wall following, though primitive, allows me to code in C right in the STM32, and take 115.2kbps serial from the XV-11 lidar directly, something the hykoku USB-only lidars cant do. If I can do all this, it would be a huge advantage instead of dragging around huge expensive boards. we have an all up weight limit of 1.5kg drone, avionics all of it.
Patrick, Thu Aug 08 2013, 03:48PM
I see your wall following pic, and its already easier than you've drawn.
well maybe wall following is the way to go ? I do have a 45 foot max range lidar. I don't actually have to physically traverse the wall do I ? (as long as the lidar returns a definite wall and not more unexplored frontier.)
as for it being easier than you've drawn. we have several doors, some without signs, 3 with signs. "ministry of torture", 'security chief" and one other, and were guaranteed that the goal object is in the security chief's office. ive been able to read all of the signs already with a special device I have using OCR. so I think I would only need to wall follow the hallway and one room. this pic is of this years challenge.
pic:
if I can read the signs I don't need to search more than the hallway or at worst 2 rooms deep.
does the bot have to physically follow the wall?
using wall following, though primitive, allows me to code in C right in the STM32, and take 115.2kbps serial from the XV-11 lidar directly, something the hykoku USB-only lidars cant do. If I can do all this, it would be a huge advantage instead of dragging around huge expensive boards. we have an all up weight limit of 1.5kg drone, avionics all of it.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Thomas W, Thu Aug 08 2013, 04:36PM
How will the robot know what the object is, like it might try pick up the corner of the table if you dont know where or what the object is?
Thomas W, Thu Aug 08 2013, 04:36PM
How will the robot know what the object is, like it might try pick up the corner of the table if you dont know where or what the object is?
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Patrick, Thu Aug 08 2013, 06:38PM
the Michigan team last year dangled a nylon cord with super magnet, then picked up a chair and it flung their machine in a circle toward the ground, where it blew apart into tiny pieces.
pics wont load?
pics
well ill try to load other pics but I can only get the entrance pic to upload.
Patrick, Thu Aug 08 2013, 06:38PM
__=|(:3)-|--{__ wrote ...
How will the robot know what the object is, like it might try pick up the corner of the table if you dont know where or what the object is?
I have a special camera, it prefers and discriminates colors, can generate bounding boxes with a centroid and ive been able to read the Arabic signs with it as well. How will the robot know what the object is, like it might try pick up the corner of the table if you dont know where or what the object is?
the Michigan team last year dangled a nylon cord with super magnet, then picked up a chair and it flung their machine in a circle toward the ground, where it blew apart into tiny pieces.
pics wont load?
pics
well ill try to load other pics but I can only get the entrance pic to upload.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Patrick, Sat Aug 10 2013, 12:41AM
Carbon Rod, appreciate link, I continue to read about Markov decision making process. its complicated, though I sort of see it as capable of initiating decision lists. certainly easier than SLAM/hector like path planners. I may choose this Markov or a similar notion.
so im thinking, the Lidar should have its left most radius and theta being the left side distance and the right side would be the same. so a PID loop would receive a polar coordinate input, and output to the yaw axis, trying to center itself in the hallway.
when the left and right distance is nearly equal the PID yaw output would be nearly centered. altitude would be a single IR beam looking downward with PI loop.
but how do I hold a predictable forward speed? can the accelerometer do this? odometry appears to be next on the list...
looks like this explains why.
I don't know what resolution my gyros have or if its practical to correct the tilt error with cosine and correct continuously for the accels orientation in 3 axis.
edit: im thinking now it would be better to take an orthogonal local map, then advance 1 foot, then make another orthogonal map, and subtract in X and Y axis, with time to find velocity, since there are no parallel lines longer than my lidars view.
Patrick, Sat Aug 10 2013, 12:41AM
Carbon Rod, appreciate link, I continue to read about Markov decision making process. its complicated, though I sort of see it as capable of initiating decision lists. certainly easier than SLAM/hector like path planners. I may choose this Markov or a similar notion.
so im thinking, the Lidar should have its left most radius and theta being the left side distance and the right side would be the same. so a PID loop would receive a polar coordinate input, and output to the yaw axis, trying to center itself in the hallway.
when the left and right distance is nearly equal the PID yaw output would be nearly centered. altitude would be a single IR beam looking downward with PI loop.
but how do I hold a predictable forward speed? can the accelerometer do this? odometry appears to be next on the list...
looks like this explains why.
I don't know what resolution my gyros have or if its practical to correct the tilt error with cosine and correct continuously for the accels orientation in 3 axis.
edit: im thinking now it would be better to take an orthogonal local map, then advance 1 foot, then make another orthogonal map, and subtract in X and Y axis, with time to find velocity, since there are no parallel lines longer than my lidars view.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Steve Conner, Sat Aug 10 2013, 09:44PM
I'm not an expert in these things, but I think it might be fruitful to use the Lidar output to build some kind of graph or tree structure in memory, that represents the walls and their edges and corners. Maybe you generate a new node in the structure every time you find a discontinuity in the Lidar distance reading, as this would represent a corner.
The wall following algorithm would be able to walk this graph instead of physically driving the robot around the perimeter of every room.
Accelerometers need to be integrated to measure speed, so they are subject to drift. To test your forward speed, you could try correlation of the current Lidar output with the output from the previous timestep. Maybe you can save processing power by doing a 1-D correlation on the segments that correspond to almost straight ahead and straight astern.
Steve Conner, Sat Aug 10 2013, 09:44PM
I'm not an expert in these things, but I think it might be fruitful to use the Lidar output to build some kind of graph or tree structure in memory, that represents the walls and their edges and corners. Maybe you generate a new node in the structure every time you find a discontinuity in the Lidar distance reading, as this would represent a corner.
The wall following algorithm would be able to walk this graph instead of physically driving the robot around the perimeter of every room.
Accelerometers need to be integrated to measure speed, so they are subject to drift. To test your forward speed, you could try correlation of the current Lidar output with the output from the previous timestep. Maybe you can save processing power by doing a 1-D correlation on the segments that correspond to almost straight ahead and straight astern.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Dr. Slack, Sun Aug 11 2013, 02:18PM
This may sound like a rather roundabout way of going about it, but the general method is extremely flexible, and can easily be extended to any number of dimensions. That may not sound so useful if you only think hyper-space, but a robot arm might have 6 joints = 6 dimensions, or your flyer may have a time profile as well as a path (to fly through a thrown hoop) = 4 dimensions.
Of course as you are mapping on the fly, this only works for portions of the route you have mapped, so it's only useful for a fast back-track, or the second go.
Set up the navigable space as an N-dimensional mesh of resistors. Choose number of points as you would for any meshing solution, as few as possible while capturing enough detail. Choose resistor values to represent the cost of each portion of the path. Set your present position to ground. Set your goal to 1v. Iteratively (assuming it's too big to solve directly as a matrix) calculate the currents and node voltages. Follow the path from 0v to 1v going from node to node in monotonically increasing voltage. This gives you the shortest legal path.
I first saw this method demonstrated with a robot arm with an elbow and a wrist, that had to avoid an obstruction, and the XY grid of resistors set up was in units of the angle of each joint. Pairs of angles which put the hand into the obstruction simply had infinite value resistors, so this algorithm would never choose a path through there.
Dr. Slack, Sun Aug 11 2013, 02:18PM
This may sound like a rather roundabout way of going about it, but the general method is extremely flexible, and can easily be extended to any number of dimensions. That may not sound so useful if you only think hyper-space, but a robot arm might have 6 joints = 6 dimensions, or your flyer may have a time profile as well as a path (to fly through a thrown hoop) = 4 dimensions.
Of course as you are mapping on the fly, this only works for portions of the route you have mapped, so it's only useful for a fast back-track, or the second go.
Set up the navigable space as an N-dimensional mesh of resistors. Choose number of points as you would for any meshing solution, as few as possible while capturing enough detail. Choose resistor values to represent the cost of each portion of the path. Set your present position to ground. Set your goal to 1v. Iteratively (assuming it's too big to solve directly as a matrix) calculate the currents and node voltages. Follow the path from 0v to 1v going from node to node in monotonically increasing voltage. This gives you the shortest legal path.
I first saw this method demonstrated with a robot arm with an elbow and a wrist, that had to avoid an obstruction, and the XY grid of resistors set up was in units of the angle of each joint. Pairs of angles which put the hand into the obstruction simply had infinite value resistors, so this algorithm would never choose a path through there.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Patrick, Sun Aug 11 2013, 04:23PM
Steve Connor, im thinking about your solution and like it, but have no idea how to write the math then code it. are there example sites you can point to? wiki is the ususal general examples. do i just have imginary circles place around the perimeter of the vehical, and when the lidar sees a differecne it acts on it? (current circle) - (circle ahead) = (decision from tree). ???
Dr. Slack, yes i may have to try this method too, just because im sure ill get some of it working in one year. though not being able to deal with unexplored area is a problem.
Patrick, Sun Aug 11 2013, 04:23PM
Steve Connor, im thinking about your solution and like it, but have no idea how to write the math then code it. are there example sites you can point to? wiki is the ususal general examples. do i just have imginary circles place around the perimeter of the vehical, and when the lidar sees a differecne it acts on it? (current circle) - (circle ahead) = (decision from tree). ???
Dr. Slack, yes i may have to try this method too, just because im sure ill get some of it working in one year. though not being able to deal with unexplored area is a problem.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Steve Conner, Sun Aug 11 2013, 06:18PM
I like Dr. Slack's idea. Navigation by diffusion. You are setting up a flow of some sort of virtual substance towards the goal, and just letting yourself be carried along on it.
The trick would be to set the resistor "costs" automatically from the Lidar data. Maybe you superimpose the Lidar data onto the mesh, trace rays out from the vehicle, and if the ray crosses a wall, you set all the resistors that it touches after crossing the wall to infinity. (The cost of flying into a wall is pretty high.) To save computing power, you could send your rays out through the mesh itself in "Manhattan distance".
This framework is good for navigating to a goal, but it doesn't help you figure out where the goal is in the first place. Another issue is that the mesh is relative to the space the vehicle is in, not the vehicle, so you need to know where you are to use it. Maybe it could be crossed with a Kalman filter that took input from the IMU, or maybe the whole technique could be turned on its head so the mesh moves with the vehicle.
Part of my job is designing algorithms to do weird stuff. It would be great if I could just look them up on Wikipedia.
Steve Conner, Sun Aug 11 2013, 06:18PM
I like Dr. Slack's idea. Navigation by diffusion. You are setting up a flow of some sort of virtual substance towards the goal, and just letting yourself be carried along on it.
The trick would be to set the resistor "costs" automatically from the Lidar data. Maybe you superimpose the Lidar data onto the mesh, trace rays out from the vehicle, and if the ray crosses a wall, you set all the resistors that it touches after crossing the wall to infinity. (The cost of flying into a wall is pretty high.) To save computing power, you could send your rays out through the mesh itself in "Manhattan distance".
This framework is good for navigating to a goal, but it doesn't help you figure out where the goal is in the first place. Another issue is that the mesh is relative to the space the vehicle is in, not the vehicle, so you need to know where you are to use it. Maybe it could be crossed with a Kalman filter that took input from the IMU, or maybe the whole technique could be turned on its head so the mesh moves with the vehicle.
Part of my job is designing algorithms to do weird stuff. It would be great if I could just look them up on Wikipedia.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Ash Small, Sun Aug 11 2013, 06:53PM
Just a thought, but don't you want it to stay in the centre of the corridor until it is in line with the centre of a doorway, then turn and enter the room through the centre of the doorway, then head for the centre of the room, etc?.....this approach should result in minimal risk of collision.
Prioritise collision avoidance, then prioritise room mapping, then prioritise identifying the target.....this should all be do-able with a small on-board processor.
Ash Small, Sun Aug 11 2013, 06:53PM
Just a thought, but don't you want it to stay in the centre of the corridor until it is in line with the centre of a doorway, then turn and enter the room through the centre of the doorway, then head for the centre of the room, etc?.....this approach should result in minimal risk of collision.
Prioritise collision avoidance, then prioritise room mapping, then prioritise identifying the target.....this should all be do-able with a small on-board processor.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Steve Conner, Sun Aug 11 2013, 07:10PM
Well yes, but I think that's pretty much what would happen if you implemented Dr. Slack's method. It finds the "path of least resistance" which would be pretty much right through the middle of a doorway.
Steve Conner, Sun Aug 11 2013, 07:10PM
Well yes, but I think that's pretty much what would happen if you implemented Dr. Slack's method. It finds the "path of least resistance" which would be pretty much right through the middle of a doorway.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Patrick, Sun Aug 11 2013, 07:55PM
ok ill start on some kind of model using the "least resistance" model.
But do I use radial rays (for the imaginary resistors) emanating from the lidar/vehical ? and I already have the sign/optical flow camera mostly working, with these two solved, that would leave only the velocity estimation, it could be very slow too, but its got to be a speed the computer is confident of.
how to code all this, how to code all this ? hmmm.
should I lay out a model using the least resistance method, but then what do I use for positioning in the hallway? just a left to right distance division into a PI controller, to keep it all centered?
Patrick, Sun Aug 11 2013, 07:55PM
ok ill start on some kind of model using the "least resistance" model.
But do I use radial rays (for the imaginary resistors) emanating from the lidar/vehical ? and I already have the sign/optical flow camera mostly working, with these two solved, that would leave only the velocity estimation, it could be very slow too, but its got to be a speed the computer is confident of.
how to code all this, how to code all this ? hmmm.
should I lay out a model using the least resistance method, but then what do I use for positioning in the hallway? just a left to right distance division into a PI controller, to keep it all centered?
Steve Conner wrote ...
Part of my job is designing algorithms to do weird stuff. It would be great if I could just look them up on Wikipedia.
yes, often the hardware of the system exceeds the ability needed at the moment, but no one can figure out how or what to program it to do... ive seen many college efforts go this way.Part of my job is designing algorithms to do weird stuff. It would be great if I could just look them up on Wikipedia.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Steve Conner, Sun Aug 11 2013, 08:16PM
Yup. We humans are so good at wandering into rooms and picking stuff up off desks, that we do it without even thinking.
It is immensely hard to see the process from the point of view of a computer that hasn't spent millions of years wandering the planet Earth in a quest for edible things to stuff in its mouth.
Steve Conner, Sun Aug 11 2013, 08:16PM
Yup. We humans are so good at wandering into rooms and picking stuff up off desks, that we do it without even thinking.
It is immensely hard to see the process from the point of view of a computer that hasn't spent millions of years wandering the planet Earth in a quest for edible things to stuff in its mouth.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Dr. Slack, Sun Aug 11 2013, 08:16PM
Well, if you have a big mesh of one point per corridor width, then you will plot through the centres of gaps. But if you have a finer mesh then left or right of a corridor and cutting off corners makes sense. With an arbitrarily fine mesh, you have to raise the cost once you get to within a rotor's width + tolerance from the wall, as a path any closer is very high cost.
Dr. Slack, Sun Aug 11 2013, 08:16PM
Ash Small wrote ...
Just a thought, but don't you want it to stay in the centre of the corridor until it is in line with the centre of a doorway, then turn and enter the room through the centre of the doorway, then head for the centre of the room, etc?.....this approach should result in minimal risk of collision.
Prioritise collision avoidance, then prioritise room mapping, then prioritise identifying the target.....this should all be do-able with a small on-board processor.
Just a thought, but don't you want it to stay in the centre of the corridor until it is in line with the centre of a doorway, then turn and enter the room through the centre of the doorway, then head for the centre of the room, etc?.....this approach should result in minimal risk of collision.
Prioritise collision avoidance, then prioritise room mapping, then prioritise identifying the target.....this should all be do-able with a small on-board processor.
Well, if you have a big mesh of one point per corridor width, then you will plot through the centres of gaps. But if you have a finer mesh then left or right of a corridor and cutting off corners makes sense. With an arbitrarily fine mesh, you have to raise the cost once you get to within a rotor's width + tolerance from the wall, as a path any closer is very high cost.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Patrick, Sun Aug 11 2013, 08:24PM
the conventional SLAM solution so far, has led to several destroyed bots. so im wanting a solution in C, that's not as complicated to code. using resistors in system memory seems as good as any alternative, but am I creating a mesh in x and y like a grid, or as a polar system? the lidar is polar, but the navigation doesn't have to be one or the other.
Patrick, Sun Aug 11 2013, 08:24PM
the conventional SLAM solution so far, has led to several destroyed bots. so im wanting a solution in C, that's not as complicated to code. using resistors in system memory seems as good as any alternative, but am I creating a mesh in x and y like a grid, or as a polar system? the lidar is polar, but the navigation doesn't have to be one or the other.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Ash Small, Sun Aug 11 2013, 08:56PM
Yes, the path of least resistance is through the middle, but I was thinking about how to implement the software with limited hardware.
If you map your 'mesh', then compute the path of least resistance, you could crash before the computing is complete. If you prioritise 'keeping in the middle', then plot the route as a second level priority you are much less likely to avoid a collision, due to a faster decision making process.
ie, get into the centre of the corridor, then travel to the door, then travel to the centre of the room, etc....then run your 'second level' algorythms.....
Ash Small, Sun Aug 11 2013, 08:56PM
Steve Conner wrote ...
Well yes, but I think that's pretty much what would happen if you implemented Dr. Slack's method. It finds the "path of least resistance" which would be pretty much right through the middle of a doorway.
Well yes, but I think that's pretty much what would happen if you implemented Dr. Slack's method. It finds the "path of least resistance" which would be pretty much right through the middle of a doorway.
Dr. Slack wrote ...
Well, if you have a big mesh of one point per corridor width, then you will plot through the centres of gaps. But if you have a finer mesh then left or right of a corridor and cutting off corners makes sense. With an arbitrarily fine mesh, you have to raise the cost once you get to within a rotor's width + tolerance from the wall, as a path any closer is very high cost.
Well, if you have a big mesh of one point per corridor width, then you will plot through the centres of gaps. But if you have a finer mesh then left or right of a corridor and cutting off corners makes sense. With an arbitrarily fine mesh, you have to raise the cost once you get to within a rotor's width + tolerance from the wall, as a path any closer is very high cost.
Yes, the path of least resistance is through the middle, but I was thinking about how to implement the software with limited hardware.
If you map your 'mesh', then compute the path of least resistance, you could crash before the computing is complete. If you prioritise 'keeping in the middle', then plot the route as a second level priority you are much less likely to avoid a collision, due to a faster decision making process.
ie, get into the centre of the corridor, then travel to the door, then travel to the centre of the room, etc....then run your 'second level' algorythms.....
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Steve Conner, Sun Aug 11 2013, 09:11PM
This does kind of make sense. Evolution has given us several different levels of dealing with things. For instance, when you accidentally touch a hot soldering iron, your brainstem and central nervous system overrides the higher-level decision making process and automatically pulls your hand away. It is just doing the same thing that it was doing millions of years ago when it might have been the complete control system for some sort of worm or beetle.
And what is more sinister, one particularly bloodthirsty Victorian scientist discovered that a dog with its brain removed could still stand upright without falling over, though it couldn't do much else.
Maybe you can take inspiration from this and start with the simplest possible code whose sole objective is to stay 3 feet above the floor and at least 1 foot away from any wall. It would be pretty simple to scan the Lidar data for the point with the smallest distance, and if this is less than 1 foot, move the vehicle in the direction directly opposite the point.
Then build the higher levels of path planning and decision making on top of this base, but give it the veto.
Of course this begs the question of what happens if you ever have to to fly down a corridor less than 2 feet wide. You may have experienced the situation where you burn yourself on the soldering iron and then smack your funny bone on the shelves in the process of pulling away. Dr. Slack's resistance approach addresses this more elegantly, but it may be too complex for a "brainstem" type function.
When designing software, I like to think in terms of modules, layers, and APIs between them. The lowest-level layer of your system is probably going to be the Kalman filter and IMU contraption that you find in a regular quadcopter, keeping the vehicle the right way up and making sure it goes in the direction it is commanded to. Above that, your basic collision avoidance routines.
The STM32F4 chips have about 192KB of RAM and 1MB of flash, which is certainly limited by today's standards, but you can get a lot done if you just program on the metal using C. The Raspberry Pi or BeagleBoard have about 512MB of RAM and the power of a Cray-1.
Steve Conner, Sun Aug 11 2013, 09:11PM
This does kind of make sense. Evolution has given us several different levels of dealing with things. For instance, when you accidentally touch a hot soldering iron, your brainstem and central nervous system overrides the higher-level decision making process and automatically pulls your hand away. It is just doing the same thing that it was doing millions of years ago when it might have been the complete control system for some sort of worm or beetle.
And what is more sinister, one particularly bloodthirsty Victorian scientist discovered that a dog with its brain removed could still stand upright without falling over, though it couldn't do much else.
Maybe you can take inspiration from this and start with the simplest possible code whose sole objective is to stay 3 feet above the floor and at least 1 foot away from any wall. It would be pretty simple to scan the Lidar data for the point with the smallest distance, and if this is less than 1 foot, move the vehicle in the direction directly opposite the point.
Then build the higher levels of path planning and decision making on top of this base, but give it the veto.
Of course this begs the question of what happens if you ever have to to fly down a corridor less than 2 feet wide. You may have experienced the situation where you burn yourself on the soldering iron and then smack your funny bone on the shelves in the process of pulling away.
Dr. Slack's resistance approach addresses this more elegantly, but it may be too complex for a "brainstem" type function.When designing software, I like to think in terms of modules, layers, and APIs between them. The lowest-level layer of your system is probably going to be the Kalman filter and IMU contraption that you find in a regular quadcopter, keeping the vehicle the right way up and making sure it goes in the direction it is commanded to. Above that, your basic collision avoidance routines.
The STM32F4 chips have about 192KB of RAM and 1MB of flash, which is certainly limited by today's standards, but you can get a lot done if you just program on the metal using C. The Raspberry Pi or BeagleBoard have about 512MB of RAM and the power of a Cray-1.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Dr. Slack, Mon Aug 12 2013, 05:30AM
That's the beauty of the system, the coordinates can be in any system you like. Navigation will always avoid crashing, though a path of true least cost requires that the model costs represent the true real world costs. So if you implemented a log-polar model with uniform resistors, you would find that the chosen path always avoided the origin. Angle cosines work well for robot arms.
Polar lidar results are probably too low level to be using directly in a higher level planning tool like this. I agree with Steve's layered approach. When you develop, you will want to work on very low level, or higher level seperately, and will need a well thought out API to be able to swap modules in and out. The natural coordinate system for the higher level map data will be cartesian, whatever the robot eyes see in.
Dr. Slack, Mon Aug 12 2013, 05:30AM
Patrick wrote ...
... but am I creating a mesh in x and y like a grid, or as a polar system? the lidar is polar, but the navigation doesn't have to be one or the other.
... but am I creating a mesh in x and y like a grid, or as a polar system? the lidar is polar, but the navigation doesn't have to be one or the other.
That's the beauty of the system, the coordinates can be in any system you like. Navigation will always avoid crashing, though a path of true least cost requires that the model costs represent the true real world costs. So if you implemented a log-polar model with uniform resistors, you would find that the chosen path always avoided the origin. Angle cosines work well for robot arms.
Polar lidar results are probably too low level to be using directly in a higher level planning tool like this. I agree with Steve's layered approach. When you develop, you will want to work on very low level, or higher level seperately, and will need a well thought out API to be able to swap modules in and out. The natural coordinate system for the higher level map data will be cartesian, whatever the robot eyes see in.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Ash Small, Mon Aug 12 2013, 12:53PM
The robot arm and the 'copter are fundamentally different in one respect.
The robot arm is controlled by hydraulics/steppers and can 'freeze' while a decision is made.
The 'copter' can't 'freeze', it is 'dynamic' all the time.
As Steve has explained, any form of AI should have 'self preservation' as it's priority (subject to the 'Three Laws', of course). Mapping surroundings should be second order priority, and the 'Mission' should be third order priority, in my opinion.
Ash Small, Mon Aug 12 2013, 12:53PM
The robot arm and the 'copter are fundamentally different in one respect.
The robot arm is controlled by hydraulics/steppers and can 'freeze' while a decision is made.
The 'copter' can't 'freeze', it is 'dynamic' all the time.
As Steve has explained, any form of AI should have 'self preservation' as it's priority (subject to the 'Three Laws', of course). Mapping surroundings should be second order priority, and the 'Mission' should be third order priority, in my opinion.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Patrick, Mon Aug 12 2013, 04:46PM
Steve, im still thinking on the memory problem.
as for the lidar, ill convert it to Cartesian, and the navigation grid too. Ill have immeadiate interrupts for self preservation if some minimum distance is violated.
im not sure how to code blocks of functions and then have them run as needed though, and yet still keep the PID flight controller up and given the highest priority. im looking through my book now. im not as good at this coding bit as you guys, im mostly a fabrication and electrical guy...
Patrick, Mon Aug 12 2013, 04:46PM
Steve, im still thinking on the memory problem.
as for the lidar, ill convert it to Cartesian, and the navigation grid too. Ill have immeadiate interrupts for self preservation if some minimum distance is violated.
im not sure how to code blocks of functions and then have them run as needed though, and yet still keep the PID flight controller up and given the highest priority. im looking through my book now. im not as good at this coding bit as you guys, im mostly a fabrication and electrical guy...
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Steve Conner, Mon Aug 12 2013, 07:08PM
Interrupts are your friends in this kind of situation. Typically you would set up a timer interrupt to run the flight controller tens of times per second as an interrupt service routine (ISR). Whenever the interrupt fires, the processor puts its current task to one side, executes the ISR, then resumes the original task where it left off.
Matters often come unstuck when trying to communicate between the ISR and the rest of the program. It is all too easy to bodge up some ad-hoc system of flags and variables that seems to work but actually has a hidden race condition. (I believe most of Windows 3.1 through to ME was written like this ) For all but the simplest communication tasks, you should use synchronisation objects like critical sections and semaphores, and then you have to watch out for deadlock.
My favourite method nowadays is a STL queue protected by critical sections. The critical sections protect the queue from race conditions (needed as the STL is not thread safe) and the queue protects the critical sections from deadlock (operations on a queue never block) so it "just works".
Steve Conner, Mon Aug 12 2013, 07:08PM
Interrupts are your friends in this kind of situation. Typically you would set up a timer interrupt to run the flight controller tens of times per second as an interrupt service routine (ISR). Whenever the interrupt fires, the processor puts its current task to one side, executes the ISR, then resumes the original task where it left off.
Matters often come unstuck when trying to communicate between the ISR and the rest of the program. It is all too easy to bodge up some ad-hoc system of flags and variables that seems to work but actually has a hidden race condition. (I believe most of Windows 3.1 through to ME was written like this
) For all but the simplest communication tasks, you should use synchronisation objects like critical sections and semaphores, and then you have to watch out for deadlock. My favourite method nowadays is a STL queue protected by critical sections. The critical sections protect the queue from race conditions (needed as the STL is not thread safe) and the queue protects the critical sections from deadlock (operations on a queue never block) so it "just works".
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Ash Small, Mon Aug 12 2013, 07:41PM
This is exactly what I'd do.
Ash Small, Mon Aug 12 2013, 07:41PM
Steve Conner wrote ...
Interrupts are your friends in this kind of situation. Typically you would set up a timer interrupt to run the flight controller tens of times per second as an interrupt service routine (ISR). Whenever the interrupt fires, the processor puts its current task to one side, executes the ISR, then resumes the original task where it left off.
Interrupts are your friends in this kind of situation. Typically you would set up a timer interrupt to run the flight controller tens of times per second as an interrupt service routine (ISR). Whenever the interrupt fires, the processor puts its current task to one side, executes the ISR, then resumes the original task where it left off.
This is exactly what I'd do.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Patrick, Tue Aug 13 2013, 11:34PM
im looking up all my old homework on ISRs for the STM32/ arm cortex stuff now.
Patrick, Tue Aug 13 2013, 11:34PM
im looking up all my old homework on ISRs for the STM32/ arm cortex stuff now.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Patrick, Thu Aug 15 2013, 02:53AM
im laying up carbon and glass composite right now. im putting together a more capable tri-copter, just for path planning demonstration. it will have a 2 kg lift capability and the ability to fly through human doorways and halls.
im not abandoning my bi-copter, but that tech isn't capable or mature enough yet.
Patrick, Thu Aug 15 2013, 02:53AM
im laying up carbon and glass composite right now. im putting together a more capable tri-copter, just for path planning demonstration. it will have a 2 kg lift capability and the ability to fly through human doorways and halls.
im not abandoning my bi-copter, but that tech isn't capable or mature enough yet.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
BigBad, Fri Nov 29 2013, 05:11PM
For shortest path calculation, the Dijkstra algorithm runs quickly and is simple and can deal with loops.
BigBad, Fri Nov 29 2013, 05:11PM
For shortest path calculation, the Dijkstra algorithm runs quickly and is simple and can deal with loops.
Re: Robotic Path Planning In 2D, How Simple or Complicated Can It Get?
Shrad, Fri Nov 29 2013, 05:42PM
there are game path finding algorithms available in python or other simple languages which would be able to run on such systems as STM32
Shrad, Fri Nov 29 2013, 05:42PM
there are game path finding algorithms available in python or other simple languages which would be able to run on such systems as STM32
Print this page