Robotic Path Planning In 2D, How Simple or Complicated Can It Get? / Computer Science / Forums

Forums

4hv.org :: Forums :: Computer Science

« Previous topic | Next topic »

Robotic Path Planning In 2D, How Simple or Complicated Can It Get?

previous 1 2 3 next

Move Thread

LAN_403

Patrick

Sun Aug 11 2013, 04:23PM

Registered Member #2431 Joined: Tue Oct 13 2009, 09:47PM
Location: Chico, CA. USA
Posts: 5639

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.

Steve Conner

Sun Aug 11 2013, 06:18PM

Registered Member #30 Joined: Fri Feb 03 2006, 10:52AM
Location: Glasgow, Scotland
Posts: 6706

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.

Ash Small

Sun Aug 11 2013, 06:53PM

Registered Member #3414 Joined: Sun Nov 14 2010, 05:05PM
Location: UK
Posts: 4245

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.

Steve Conner

Sun Aug 11 2013, 07:10PM

Registered Member #30 Joined: Fri Feb 03 2006, 10:52AM
Location: Glasgow, Scotland
Posts: 6706

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.

Patrick

Sun Aug 11 2013, 07:55PM

Registered Member #2431 Joined: Tue Oct 13 2009, 09:47PM
Location: Chico, CA. USA
Posts: 5639

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.

Steve Conner

Sun Aug 11 2013, 08:16PM

Registered Member #30 Joined: Fri Feb 03 2006, 10:52AM
Location: Glasgow, Scotland
Posts: 6706

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.

Dr. Slack

Sun Aug 11 2013, 08:16PM

Registered Member #72 Joined: Thu Feb 09 2006, 08:29AM
Location: UK St. Albans
Posts: 1659

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.

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.

Patrick

Sun Aug 11 2013, 08:24PM

Registered Member #2431 Joined: Tue Oct 13 2009, 09:47PM
Location: Chico, CA. USA
Posts: 5639

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.

Ash Small

Sun Aug 11 2013, 08:56PM

Registered Member #3414 Joined: Sun Nov 14 2010, 05:05PM
Location: UK
Posts: 4245

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.

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.

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.....

Steve Conner

Sun Aug 11 2013, 09:11PM

Registered Member #30 Joined: Fri Feb 03 2006, 10:52AM
Location: Glasgow, Scotland
Posts: 6706

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.

previous 1 2 3 next

Moderator(s): Chris Russell, Noelle, Alex, Tesladownunder, Dave Marshall, Dave Billington, Bjørn, Steve Conner, Wolfram, Kizmo, Mads Barnkob