USDrobotics started with a simple question: “How can we create an Unmanned Aerial Vehicle (UAV) that is truly safe for almost any application?” Our inescapable conclusion: Take the human pilot out of the equation. That one was actually pretty easy, virtually everyone (except the FAA) recognizes the necessity of autonomy. The second result from our research, however, was a little less intuitive: You have to get rid of the computer, as well.
In a word, what makes drobots unique is Architecture. Almost every other attempt at autonomy is being pursued as a software solution. The problem is that general purpose computers are designed to everything poorly. They will do anything, but the inevitable consequence of that flexibility is the fact that they do not do any one thing particularly well. Hardware accelerators, by contrast, are specially designed supercomputers built to do one thing very, very well. In our case, these hardware accelerators form the basis of our pilot, navigator, and obstacle avoidance / scene analysis systems. Hardware systems have the added benefit that they cannot be hacked. What we strive for is safety. Safety implies accuracy, and accuracy demands high speed supercomputer power. The challenge is how to get that inside a small, mobile, platform.
The hardware architecture is layered, such that the computing platform is designed to meet the speed and data requirements of that layer. Rather than a “one size fits all” general purpose computer, the computer is made to fit the data, not the other way around. In this way, each layer greatly simplifies they layer(s) beneath it.
Because each layer is so different in data requirements and computing resources, we have different architectures for three different systems – Navigator, Pilot, and Obstacle Avoidance.
In the top layer of the architecture, one of the most data and computing-resource intensive problems is calculating the autonomous path through a cityscape from A to B, cooperatively plotted with other vehicles, timed to the second and calculated to the centimeter. When it’s put that way, one realizes there are only two real solutions – all data for all vehicles needs to be shared by every vehicle in real time, or the path is precomputed by a server farm with any amount of processing power necessary and access to any amount of data required. Essentially all a precomputed path system needs is a server farm and a 3D map of the world, both of which Google basically already has.
The last piece of the puzzle is the algorithm to compute the paths. USDrobotics has that in the form of a 4D autorouter system, which can calculate the paths of any number of vehicles, essentially all at the same time, with cooperative knowledge of all of the vehicles – the Trackpath.
Once the Trackpath is defined, it is loaded into the vehicle. This greatly simplifies the definition and design of the next layer of the architecture, the hardware supercomputer that forms the on-board navigator. In simplistic terms, the navigator – dubbed STeVIE (Safe Temporal Vector Integration Engine) – simply calculates the difference between where the platform is now, and where the trackpath says it’s supposed to be.
In an existing UAV system, this difference might be calculated every hundred milliseconds or in the case of a GPS fix much slower, which is a significant source of error at speed. Because STeVIE is a hardware supercomputer, it’s calculating this difference every thousandth of an inch. This changes everything about how the system is designed and operated. This is what makes it accurate, repeatable, and safe. The navigation supercomputer’s task is simplified because with the trackpath already calculated it can model itself as a simple point in space and the calculation is reduced to computing a single vector of where the platform should go in the next one millionth of a second. Another common problem with navigation systems is that up to six different coordinate systems are used depending on the point of view the platform is trying to accommodate. There’s the base coordinate system – the platform itself, the pilot’s, the inertial reference system, etc. Because there’s no pilot, and the trackpath has simplified required knowledge of the surroundings, STeVIE only has one reference system to deal with.
Of course, just looking at where we are versus where we want to be isn’t the entire story, it’s not even the most interesting part of the story. The interesting part is all of the other vectors that also have to be considered to get the final vector which is STeVIE’s end result. Above is a basic diagram of STeVIE’s architecture. The architecture is almost deceptively simple: Vectors that represent the “desired” navigational path of the platform come from a number of sources, and STeVIE’s purpose is simply to add these together to get the final result. This is the “Temporal Vector Integration Engine.” The vectors come from:
- The baseline vector from the Trackpath system – where I am vs where I should be.
- The Free Flight Corridor (FFC) or fence vector.
- Obstacle Avoidance
- (Optionally) other vectors such as formation flying or swarm information.
One might argue that the speed of the processor doesn’t matter, because the information available to the processor such as the GPS fix or Inertial Measurement Unit (IMU) is coming out so slowly that the speed of the processor doesn’t matter. This is less than accurate on two counts: 1) these general purpose computer software systems are often built with multiple “tasks” which in the mind of the programmer operate simultaneously. In reality there’s still only one computer and it has to switch rapidly between these tasks – with significant overhead each switch – to process all of them as near to simultaneous as it can. The computer is basically already overloaded and speed really does matter. Each task added exponentially increases the complexity, debugging, and testing necessary to complete the software. Hardware, on the other hand, is naturally multi-tasking and without the overhead of the operating system and tasking systems much faster. 2) One of the USDrobotics patents is on the design of a predictive vector interpolator (PVI) or “vector interpolator”.
Given a history of known points on a graph, interpolation is a standard technique for calculating the locations of unknown points in between any of the known points. In Predictive Interpolation, the hardware computes multiple derivatives of the change in distance to track the velocity, acceleration, and jerk over time which allows it to predict with high resolution the series of the next points without knowing the final point in advance. This is critical in maintaining high accuracy of a vehicle’s path in real time. For example, a drone’s GPS receiver might only be returning location information several times per second. Because the difference between the baseline vectors is so small due to STeVIE’s inherent speed, we use this interpolation to feed sensor information to STeVIE at a much higher rate.
The second vector is derived from the Free Flight Corridor (FFC) derived by the 4D autorouter when the trackpath was created. USDrobotics is the first to propose (and apply for patents on) the concept of a 4-dimensional Inverse-GeoFence. Instead of defining the multitude of places the drones cannot go, we define a single 4D structure (In Space and Time) that defines the only area where it is allowed to go. This again changes everything about how the vehicles are designed, programmed, and operated to greatly simplify their design while simultaneously making them safe and mitigating the ability of a terrorist to misuse a drone platform to cause harm. Drobots simply cannot go where they’re not approved to go. If the GPS receiver is blocked or disabled, it simply doesn’t fly. Only one fence structure is ever needed within the platform.
It is this structure that simultaneously makes the platform safe from misuse, allows it to be cooperatively managed with all of the other vehicles in the airspace, and allows it sufficient freedom of action for obstacle avoidance. More information on the fencing structure can be found in our white papers on trackpath definition and design.
This FFC vector influences the platform’s path if and when the platform approaches the fence. Operationally, there are two fences, the outer or “hard” fence which the platform is not allowed to cross without declaring an emergency, and in inner “soft” fence that has the initial influence on the flight path vector. The soft fence can be calculated based on a number of criteria – the maximum speed of the platform, its current speed, and input from the obstacle avoidance system, for example. To keep this description simple, let’s assume that the soft fence is calculated such that it is inset from the hard fence depending on the velocity of the platform. If the platform is moving fast, the soft fence will be farther away from the hard fence, and if the platform is moving slowly the soft fence will be closer.
Once the platform crosses the soft fence, the FFC system will produce a vector directing the platform away from the fence. One can assume that the only way it approached the fence in the first place was either a mechanical failure or external force such a wind, and the baseline vector should already be trying to get the platform back onto the trackpath. The FFC vector will add into this vector to indicate an increase of more speed/power is required. If the path cannot be corrected and the platform encounters the FFC boundary itself, the Terminal Guidance system takes over and the platform declares an emergency.
The next vector is input from obstacle avoidance. This system’s job is to assess the environment in as many directions as possible, and assess whether the platform’s flight path needs to be altered given any unexpected obstacles it may encounter in real time. This system produces another vector that is summed by STeVIE into the final path vector at that moment in time.
Finally, other application specific vectors from the scene analysis or other system can easily be integrated into the architecture. This might include formation flying or swarm behavior vectors.
The end result is a simple vector that is passed to the next level of the overall platform architecture.
In the final level of the architecture, another supercomputer is tasked as being the pilot of the vehicle. It doesn’t need to know the destination, or the path, or anything else except what is the current state of the platform, and what has to be changed in the platform to execute the vector passed down from STeVIE.
Because of the speed of the platform and the layered hierarchy, each level is greatly simplified by the computation of the layer above it. This is of great importance because it significantly reduces the amount of design effort required at each layer, and the interactions between the tasks – a nightmare in software based systems – is also controlled and simplified. This makes Drobots simpler to design, simpler to simulate and test, and simpler to build than software-based solutions. This will allow us to catch up and even leap ahead of companies that have trudged on for years refining their software models.
This supercomputer is dubbed VIGO for Vector In Guidance Out processor. The timing and processes of the real world platform come into play in this system, and must be taken into account. These processes are often non-linear in nature. Standard computing systems often simply approximate non-linear systems so ease the computational burden. VIGO is designed to be customizable to the performance characteristics of the platform. It utilizes non-linear techniques such as neural networks and fuzzy logic to control the platform with increased accuracy and high agility. Some platforms may have simplistic quadrotor design, and VIGO handles the motor speeds with non-linear techniques such as fuzzy logic. Other platforms may need the agility and high speed of voice-coil actuated gimbals on ducted fan engines and a more robust combination of techniques would be applied.
The drobotic concept, however, does not stop there. The trackpath excels at designing a path over any distance taking all other structure and vehicles into account, but it can’t know everything. One or more instances of a third supercomputer architecture, the Flexible Pipeline Processor (FFP) is tasked with obstacle avoidance and scene analysis. Both of these are critical to drobotic function. Obstacle avoidance is a simple concept, but not always easy to realize. This hardware accelerator is again simplified by the fact that most things are taken into account by the trackpath.
Pipeline processors are not a new concept, the sequence of mathematical operations required for a result are built as hardware steps instead of lines of software code. As the result of the first step feeds into the second a new piece of data is fed into the first, and result to the second, and the third and so on until the pipeline fills, and at that point you are getting one result every clock cycle. The problem with pipelines is they cannot branch, and software code, on the average, branches every 3 to 5 steps. So pipelines are used, but are hardly ever more than 3 to five steps long.
USDrobotics has developed the first pipeline architecture with branching capability, which places this particular supercomputer somewhere in between the capabilities of hardware accelerators such as STeVIE and VIGO, but still much faster than a standard computer. It is not quite as programmable as a standard computer, but it is more programmable than a hardware accelerator and it excels at matrix-based data sets or high throughput problems such as imaging and pattern recognition. These unique and proprietary processors are crucial to the overall architecture of an autonomous system.
Of equal import is a significant shift in thinking about how to protect people from misuse of drones. All existing “drones” use the concept of a GeoFence. This fence defines a polygon on a map where the drone is not allowed to go. This is fundamentally flawed on a number of levels:
- A GeoFence doesn’t always work if the drone starts out inside the fence, such as the 3-mile exclusion zone near an airport.
- It takes a sophisticated piece of equipment – a couple of square inches of aluminum foil or a gum wrapper, for example – to defeat the geofencing system and fly wherever you want. This is fixable, but is the current implementation in many platforms.
- If the number of GeoFence constructs grows, for example if legislation allows a homeowner to request that drones not fly over their property like the “don’t call” list for telemarketers, the CPU handling the flight control will be quickly overcome by the real-time processing requirements of too many fences, even if only the fences in the Area of Operation are included. The general purpose computer has a lot of tasks to perform, and the more time it spends trying to process geofences, the less time it has for other tasks.
- The GeoFencing structures must be continuously updated to every platform as they change.
- GeoFences, in essence, are 2-Dimensional structures when they really need to be 3D or even 4D (space and time).
USDrobotics is the first to propose (and apply for patents on) the concept of a four dimensional Inverse-GeoFence, also known as a Free Flight Corridor. Instead of defining the multitude of places the drones cannot go, we define a single 4D structure (In Space and Time) that defines the area where it is allowed to go. This again changes everything about how the vehicles are designed, programmed, and operated to greatly simplify their design while simultaneously making them safe and mitigating the ability of a terrorist to misuse a drone platform to cause harm. Drobots simply cannot go where they’re not approved to go. If the GPS receiver is blocked or disabled, it simply doesn’t fly. Only one fence structure is ever needed within the platform.
Of greater import is the scene analysis system – drobots can not only detect conditions and objects in their vicinity, but they can be programmed to act upon that knowledge. This is one of the most important breakthroughs that defines a drobotic vehicle. Instead of thinking of a drobot as a “drone” that someone is out there piloting remotely, we now think of it as a computer that moves things. This shift in fundamental computing has not been seen since the advent of the microprocessor in the 1980s, and in a similar manner we foresee that drobots – as programmable to a specific task as a computer application – will be just as ubiquitous. Being programmable is what allows drobotic platforms to make the transition from toys to tools.