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?

1 2 3 next

Move Thread

LAN_403

Patrick

Thu Aug 08 2013, 05:02AM

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

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

Carbon_Rod

Thu Aug 08 2013, 06:46AM

Registered Member #65 Joined: Thu Feb 09 2006, 06:43AM
Location:
Posts: 1155

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:

Patrick

Thu Aug 08 2013, 07:11AM

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

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!

I need something better than wall following, but less demanding than a full SLAM implementation.
let me look at your link....

Carbon_Rod

Thu Aug 08 2013, 07:31AM

Registered Member #65 Joined: Thu Feb 09 2006, 06:43AM
Location:
Posts: 1155

As this maze has no cycles, you can solve it with a follower, and "fetch routine" override....

Patrick

Thu Aug 08 2013, 03:48PM

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

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.

Thomas W

Thu Aug 08 2013, 04:36PM

Registered Member #3324 Joined: Sun Oct 17 2010, 06:57PM
Location:
Posts: 1276

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?

Patrick

Thu Aug 08 2013, 06:38PM

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

__=|(: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.

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

Sat Aug 10 2013, 12:41AM

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

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.

Steve Conner

Sat Aug 10 2013, 09:44PM

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

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.

Dr. Slack

Sun Aug 11 2013, 02:18PM

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

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.

1 2 3 next

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