Automatic route planning for UAVs

[Iraqigeek]

Would the ability to plan a route (possibly best route) on board of an RC scale UAV be worth it?

The ground operator would only have to specify a set of waypoints, and the UAV would automatically plan its route to cover those points.

To give an explanatory scenario, say you were flying your UAV in a an area with lots of hills, and you wanted to maintain a constant, and possibly low, ground altitude (for example if the UAV was tracking a car on a road).

Another possibility would be to add a new waypoint to the UAV route while in mid air, and have the UAV figure out if it can reach this point directly, or if there are any obstacles (such as a mountain) that it needs to avoid, calculating the best route to reach that point if there was an obstacle.

One interesting use, IMHO, would be for improved accuray in airial photography by adjusting the angle the camera is pointing to compensate for terrain elevation, enabling accurate GPS referencing for those photos.

I believe it is quite possible to enable make such a system with a gumstix and GPS input only. The gumstix would be able to carry terrain info covering an area about the size of Australia (yes, Australia).

So, is it worth it to develop such a system?

[kd7ost]

Yes, absolutely.

Dan

[Iraqigeek]

Just want to add that there is nothing revolutionary here, and I was quite surprised that no one had this idea until now.

The whole idea goes around DEM (Digital Elevation Model) data that is widely available on the net, and if you pay a few bucks, its possible to obtain data with a resolution of 100M (~300ft) of spatial resolution, but with elevation accuracy of 10M (~30ft).

As for the ability to pack elevation info of huge areas of land, thats just plain old compression (I was thinking of ZIP). The elevation data is highly compressable because you dont usually have steep changes in elevation between consecutive samples, which renders the data highly compressable. Deviding the elevation data carried on board into rectangles of about 100x100km (60x60 miles) would enable the xscale processor on board the gumstix to decompress the data one part at a time, with virtually no delay.

Other than that, the route planning consists of applying simple collision detection algorithms and some simple, but efficient space search algorithm. The whole code shouldn't be that large, nor require any substantial amount of processing power to run.

[kd7ost]

I think the idea has been implemented in full scale aviation. In fact a bit more. You can get systems that overlay loaded maps in a view screen. Based on GPS information with respect to altitude as well as Lat and Lon you can get a 3D map of the area you are flying as well as seeing your position within that graphic. You can see terrain in cloudy sky or night time without radar. Something like a Google Earth image.

There would be high interest in seeing what you describe actually implemented successfully.

Dan

[poynting]

The big problem with DEM data is that because it is in such a large grid, terrain features smaller than those squares are lost. It is possible to completely miss a small hill with a considerable elevation rise. The method is good if you're a considerable distance above ground (300-500ft or so), such that you can avoid the largest hills, but for lower-altitude navigation, you can't really trust the data enough to be 100% sure that nothing is there. Also, I do not believe that DEM data accounts for buildings, which become a big issue at lower altitudes. I am sure the data does not account for vegetation - in many places trees are 120 feet high.

One question is that, apart from making the UAV somewhat 'autonomous', what do you gain by storing the data on the aircraft as opposed to storing the data for the entire world on your ground station PC and re-routing based on that? The ground station will be able to support a lot more complex processing and store much more ground data, and will just have to issue re-route commands in real-time. Since you're re-routing from the ground anyway, why not send the aircraft a 'safe' route based on the ground station's calculations? I think this would provide the fuctionality you're looking for with considerably less effort - any autopilot that accepts re-route commands could be compatable.

[Iraqigeek]

poynting,

I was able to find DEM data with a resolution of 100M (~330ft), which gives a pretty good resolution, even for small hills. By using interpolation, it is quite possible to get good estimates of the ground elevation in between those samples, say down to 25M (~80ft). With a little extra effort, its possible to obtain DEM data with sample resolutions going down to 25M (~80ft). How many hills do you know of that are over 300ft high, with a radius under 300ft???

I was thinking of the UAV flying at 400-500ft above the ground, which gives a rather safe clearance, even with high trees in the area. As for urban areas, you could easily complement the DEM data with information about certain areas where the UAV should have provide extra clearance (maintain an extra 200ft from whatever altitude the UAV was holding).

As for the advantage of having the data on board, first, it would greatly reduce the amount of data that has to be relayed to the UAV. Instead of having to relay 10s or even 100s of waypoints when the terrain altitude under the UAV is in constant change, you will only need to relay the destination waypoint coordinates. It also increases the level of autonomousy of the UAV. You can simply use SMS messaging through GSM, or even a satellite phone to insert new waypoints, and have the UAV figure out its route to reach that point.

Like I said before, having the elevation data on board will enable a wide range of applications. You can tell the UAV to take high resolution photos for a given location based on its longitude and lattitude, and the UAV, using the DEM data, would be able to accurately point the camera, and correct the UAV altitude to obtain the best shot possible, compensating for the ground elevation of that location, so the user doesnt have to care whether the location is at sea level, or on top of a 10,000ft high mountain.

With some more detailed info about the UAV itself, like fuel consumption rate with regard to throttle opening, climb rate and speed capabilities, you could even have the UAV figure if its more fuel efficient to climb and go over a hill/mountain, or plan a flight path that goes around this hill/mountain. In extreme cases, the UAV would be able to find a suitable safe place for an emergency landing instead (for example if it doesnt have enough fuel to reach back to base) and inform the ground operator ahead well ahead of its planned alternate landing location.

Basically, the system I am proposing will rely on pretty old 2D collision detection algorithms. Since you will not have any moving objects flying, other than the UAV, nor any objects hanging from the sky, there is no need to include the Y-axis for the calculations (operating on the XZ plane), and then simply calculating the altitude clearance between the UAV and ground at each point along this path. If the difference would be less or more than a predefined range (say min 400ft, max 600ft) the system could adjust the altitude ahead of time.

Adding other terrain information to complement the DEM data wouldnt be hard, nor require a lot of space. To define a forest, you simply define a polygon of the forest boundaries, and the average ground altitude of trees/vegetation within this forest/polygon. Then using simple 2D tests to determine if the UAV is inside or our of this polygon. The same applies for urban areas or cities, just define a ploygon, and integrate it with the DEM data for that sector, so the system would only have to care whether the UAV is near, in, or going to enter this area only if the UAV will be passing through this sector.

[Bg~]

SRTM data is 30 meter resolution, and available as a free downlaod from the USGS.

http://srtm.usgs.gov/data/obtainingdata.html

And this is most definately not the first time someone has had this idea. Cruise missiles for one.

Edit:
http://www.dgadv.com/aerotracker/ (ground based)

You might search for "UAV terrain following" on google scholar (scholar.google.com) too.

[Iraqigeek]

Bg~,

The USGS has 1-arc second (30 meter) data for the US only.

I know I wasnt the first person to think about this. My surprise was that with so many UAV autopilots available on the net, none seemed to offer such functionality.

What I was thinking of falls, indeed, inline with aerotracker, but adjusting the altitude, and possibly the flight path depending on parameters set by the ground operator.

As for terrain following, doesnt that usually refer to scanning the terrain under the UAV with a radar and matching the scanned data with terrain elevation of the planned path to guide the UAV to its target.

[kd7ost]

I know I wasnt the first person to think about this. My surprise was that with so many UAV autopilots available on the net, none seemed to offer such functionality.

Why would that surprise you? What benifits to that type of flying are there?

Dan

[Unterhausen]

In the early 90's, I worked on a system that did this for a fighter. I was mainly a method to keep the pilot from flying into the ground, which is a big problem for planes like that. The big technical revolution was to get 30 megs of ram to hold the data. On the other hand, most computers still had less than 4 megs or ram.

Obviously, it's an interesting problem, but I'm not sure doing this will yield much.

[hugo_vincent]

I think this is a cool idea but still can't see why this needs to be done onboard the aircraft...

All the points Iraqigeek pointed out above in #6 would work exactly the same with the data on the groundstation laptop. THE TERRAIN OBVIOUSLY DOESN'T CHANGE! Only the route does.

AFAIK the amount of data to be sent is only a single waypoint (maybe 10 bytes of data), say, every 100 m (worst case, especially if the terrain data is on a 100m grid). If the plane is flying at 100 kmph that is only about 3 bytes/second. And if you used data compression (because as you said, most of the time, the difference between each waypoint is small so it compresses well, e.g. delta coding) and some kind of "parametric interpolation" (explained below) you could easily get down to, say, 1 kByte per minute of data over the radio link.

What do I mean by "parametric interpolation": I don't really know what this technique is called but I remember reading about it somewhere. You fit an equation to a set of waypoints (say one equation for every 1-10km along the route) and send the equation instead of the waypoints. And the onboard autopilot can interpolate waypoints at the desired separate (say every 100 m) along the planned route.

The bandwidth numbers I gave above (dispite being guesses), assume you need a waypoint every 100 m (meaning roughly every 3 seconds of flight at 100 kmph) and for a constantly changing route. In reality, I would imagine for a normal UAV flying at say 70 kmph, over normal terrain (not extermely variable), you would probably only need about 1-10 kbytes of data for any given route change.

Also, its easier to do these computations on a PC, especially since the operator can look at the proposed auto-planned route on a map on the screen and check it is sensible.

Really, the only advantage of having the route planning on board that I can think of would be for very automous UAVs that basically have no ground station (just a GSM cellphone with SMS).

If you do decide to give it a go (either onboard on on the groundstation), investigate cost-based search techniques. I think such a technique would produce a much better route than a simple collision detection method. It would work by applying a predetermined set of "costs" to each "event" such as turning or climbing or decending, and search possible routes tallying up the total cost. The route with the smallest cost is used. The cost in this case is proportional to the amount of fuel or battery power used to complete the route. For instance, a route that climbs and descends a lot (to negotiate hilly terrain) would have a high cost as a lot of fuel is burnt each time it climbs, and a route that makes lots of tight turns would also have a higher cost than a route with a few gentle turns (because the aircraft has higher drag while turning). The cost function can also be used as a heuristic for the terrain search; as soon as the cost passes some threshold (e.g. the cheapest cost so far) you can just stop testing that route because its not the cheapest.

Keep us posted with what ever you end up implementing, because this really is an interesting problem.

Cheers,
Hugo.

[Iraqigeek]

Dan,

it surprises me because its netither computetionally expensive, nor that complex to achieve. If you strip it down to just terrain avoidance without any route planning or following criteria, the problem becomes rather simple to solve. Even with a few KBs of space, its possible to store terrain info for relatively large areas. Its not processor intensive either, which means that it can be implemented using cheap microcontrollers without adding much to the total cost of the hardware, nor the power required to operate the autopilot.

Hugo,

A heuristic search is exactly what I had in mind, back when I was doing my masters, I did some space search programs relying on genetic algorithm heuristics, which can reduce computetional cost exponentially if you can have a solid criteria on how close you are to solving the problem. However, to measure whether a new point along the path path is successful, you will have to rely on collision detection, so you can keep the UAV within your predefined flight criteria WRT altitude. In any case, from the info I gathered until now, all the algorithms involved can be run relatively fast on ancient 286 or early 386 machines as most come from good old 2D games.

The way you plan the flight path is totally depandant on the mission at hand. When you are following a moving ground object, the UAV MUST follow a certain exact path, no matter how costly this path is in terms fuel/power.

As for insisting on having the calculations done onboard. Working as a wireless network engineer for a few years has taught me to NEVER rely on a wireless link for any mission critical task (why do you think mobile operators cover any given point by at least two ground stations? and in urban areas that can go as high as 4). You can never trust the environment in which you will be operating, and the amount of interference that yo may encounter. Having everything on board, minimizes the amount of data that needs to be exchanged. I know that doing it on the ground doesnt consume a lot of bandwidth (even without any form of compression, just some smart data representation schemes), but the less data that needs to be exchanged, the less dependant on the ground station the UAV will be (supposing that the software is _relatively_ bug free).

I also used to work on satellite phones, and while talking on those phones is quite expensive, exchanging SMS messages is very affordable. I know this is taking it to extremes, but you could navigate the UAV from virtually any place around the world provided that you have a clear view of the sky. A more reasonable approach would be to use a GSM module on board. Either way, data exchange is minimal, which translates into a more reliable vehicle and reduced operational costs (as far as the flight electronics are concerned).

Its relatively easy to simulate the operation of the route planning algorithm on the ground station since it only depends on DEM data and the list of waypoints for the current flight.

From my experience as a network engineer, you shold never rely on your communication line/link. As a computer science graduate, its always better to minimize the amount of data exchange between the nodes of your system to the minimum. The more you rely on communication exchange, the more downtime your system will have.

I will not start to work on this anytime soon, as I am looking for a new job, studying for a few IT certifications, and working on another couple of projects. For now, its still in the R part of R&D which means lots of reading, looking around, and trying to collect as much feedback as possible as to how to approach this. I hope to be able to start working on this around April, if all goes as planned.

[clolson]

SRTM data is 30 meter resolution, and available as a free downlaod from the USGS.

http://srtm.usgs.gov/data/obtainingdata.html

And this is most definately not the first time someone has had this idea. Cruise missiles for one.

Edit:
http://www.dgadv.com/aerotracker/ (ground based)

You might search for "UAV terrain following" on google scholar (scholar.google.com) too.


One quick comment. I've done some work with SRTM and SRTM2 data in the context of FlightGear. (www.flightgear.org). Generally it is very good data, but there are places where it has odd discrepancies such as a localized peak where one doesn't exist due to some noise in the data collection or processing. It also has many 'voids' where the elevation simply isn't known. Often these are small areas, often over water/lakes/etc. so you can interpolate through them, however, there are some notable exeptions to that. 1/2 the grand canyon (on the eastern side) is missing. A huge chunk of Rhode Island is missing. Often these voids happen where there are sharp or extreme elevations changes. Many mountain tops get lost because of this.

So my point is that you need to be careful with this data, it's not perfect. It's pretty good for most areas, but you really want to some how validate the data set for your flying area before you really start to depend on it. And you would probably want to have some sort of backup sanity check system in place ... whether that be a ground operator monitoring the live video to make sure the ground doesn't start moving too quickly, or some sort of lasar range finder or something that can catch mistakes in your primary system and signal the need for immediate evasive action.

Curt.

[poynting]

So my point is that you need to be careful with this data, it's not perfect. It's pretty good for most areas, but you really want to some how validate the data set for your flying area before you really start to depend on it.

Speaking from the experience of doing something very similar, I would completely agree. Don't trust SRTM data below 300-400ft AGL, and even then, make sure you've validated the data for the area you're flying in. I've seen hills that were a couple hundred feet across and a couple hundred feet high just appear half their size because of how they were averaged in the data.

[treehog]

In marine navigation they maintain the same altide sea level but the ground rises up too meet them and the collide with land if they get it wrong

So most large ships have amap of the sea floor and can navigate to avoid the low points shallow water and in real time kwow the water depth in advance from tide tables so one day they might enter the region with one route of way points and the next day follow a totaly different route due to new resaons tidal influences etc

The ships carry on board the electronic maps of thier regular reions and can update from satilite or cell phones a new region if nessary

I realy fail to see any normal civilan UAV application and so its military for cruise missiles which need to hug the terrain at high speed and do this activity

In most UAV a simplex map with triangular teeth with gps reference points some hundred metres around the mountains the teeth repesent for terrain avoidance and solid cyclinders going skyward to represent no fly regions such as towns nature reserves etc

Most of the econimically important zones of the planet nowadays have good cell and wifi systems
Even in darkest africa say Cameroon they got cells for telephones in most of the country and broadband in most big towns so the issues of tempory down link drop outs in most europe or america can normally be resolved by simply lottering until the connection is resablished and in africa or remote regions a simplex map of gps avoid zones will probally be eneogh

The other more likey useful solution would be some type of small radar unit that sweeps up and down possibly a maine yaught light weight unit costing $1000 that nomally can be set to see forward turned on its side could see up down and scan the terrain in front of it and build its own real time data
there again the only use that comes to mind is to fly low to avoid a strong head wind for slow UAV
but terrain hugging would be nearly imposible to allow in Euroland as its full of church spires and crane derriks and power lines that might not show on low resolution radar
so I fugure low speed UAV in europe going to have to turn tail and land elswhere or pop open its chute and land

I am studing to try to make terrain avoidance UAV for my Dynamic soaring so that craft has a knowlege of small terrain sector and where its not to fly eg through the mountain so that if my stick inputs try to get model to hit terrain the computer will overide this and tighten turn or whatever
In that case it will probably be a few sets of gps points for the ridge and the valley floor with some programing logic that allows it to keep trying to find exit if it overflys the set points which might have a buffer of some metres
A simple Sms can update the craft if the wind switches so the other face of the ridge needs to be used

Ralf