Baskin School of Engineering faculty Ricardo Sanfelice seeks new methods for computationally aware cyber-physical systems

Ricardo Sanfelice
Ricardo Sanfelice
Friday, December 18, 2015
Karyn Skemp

New cyberphysical system approach could solve problem of crowded airways and highways

As airways and roadways become more crowded and complex, the need for safe and efficient traffic flow management becomes increasingly critical. Soon, driverless cars, unmanned aircraft and other autonomous vehicles will travel within the spaces traditionally occupied solely by piloted aircraft and cars.

How will we manage such multi-agent, heterogeneous environments? How will we ensure the safety of people and vehicles inhabiting these spaces, while also ensuring that aircraft, cars and other vehicles arrive at their intended destinations at the intended time, and – in some cases – accomplish their intended missions?

The answer, possibly, lies within the curious realm of computationally aware cyber-physical systems.

With a three-year grant from the National Science Foundation, Baskin School of Engineering faculty Ricardo Sanfelice, and his collaborator Jonathan Sprinkle from the University of Arizona, are planning to find out.

"As air space (or highway-space) becomes more crowded, the need to be able to react quickly to potential threats requires new techniques that are both accurate and timely," says Sanfelice.

The solution may be a cyber-physical system – an engineered system made up of computational and physical components – in which the software is aware of the hardware, and can respond in real time to its computational constraints. In other words, a computationally aware cyber-physical system.

While there are many applications for smart cyber-physical systems in agriculture, energy, transportation, building design and automation, healthcare, manufacturing and other sectors, Sanfelice’s NSF project is motivated by a specific problem: that is, the problem of synthesizing obstacle-avoiding trajectories for path-planning vehicles. A prime example of this is the opening up of the National Air Space to autonomous vehicles over the next few decades.

"The project will bring cutting-edge research on CPS to the Baskin School of Engineering’s undergraduate and graduate programs," says Sanfelice. "It also further strengthens the ties between our campus and NASA Ames, as it addresses specifically the integration of unmanned autonomous vehicles (UAVs) in the National Air Space."

The details

Motivated by a lack of algorithms that can take into account the computational limitations of real-world hardware and software, Sanfelice and Sprinkle plan to generate tools for systematic analysis and design of computationally aware algorithms in cyber-physical systems.

Model mismatch schematicTraditional models for determining a vehicle’s trajectory rely on predictive algorithms, which must have a high degree of accuracy to ensure that collisions are avoided and a minimum separation between vehicles is maintained. But accuracy comes at a cost. The more accurate the model, the more computing power is required, and the longer it takes to evaluate and optimize trajectories. This limits the ability of individual components of the system to respond quickly. In very complex environments, with multiple vehicles and other obstacles, the computational power can be prohibitive.

So the question is: How accurate is accurate enough? The answer is simple: Accurate enough to avoid collisions and maintain minimum separation constraints. Not all systems will require the same level of accuracy, but during the algorithm design stage, variables such as required degree of accuracy and computational constraints are typically omitted, which can lead to overly conservative models, sometimes severely limiting the range of possible trajectories.

What Sanfelice and Arizona collaborator Jonathan Sprinkle propose is to build in the computational limitations of the system during the design phase. In doing so, Sanfelice and Sprinkle will utilize obstacle avoidance techniques in traditional trajectory synthesis, adapted to account for that vehicle’s hardware, software, dynamics and goal. This will dramatically extend the concept of feasible trajectories, since it will consider the ability of the sensors and computational power to execute such trajectories with robust margins for control and sense-and-avoid. Obstacle and Goal

"Professor Sanfelice is one of the world’s foremost experts in hybrid systems, and this work really could not happen without such a collaboration," says Sprinkle. "I’m excited to be a part of this project because it permits us to more effectively predict the possible behaviors of these complex, physical systems with advanced mathematical and computational models."

The breakthrough is in the ability to switch between two different predictors of a system, depending on how it is going to be used. Sprinkle says, "It’s a bit like looking at a flying football and a flying baseball: footballs and baseballs will bounce in very different ways when they hit the ground—but we don’t need to take this into account when they’re flying in the air. If we did, we would get the same answers for both, but it would take a very long time to do the calculations."

The same is true for aircraft, that when they turn, climb, descend or land, different aircraft can behave in very different ways. Sprinkle says, "This work enables us to more quickly calculate how the aircraft can behave, without having to do the most complex calculations all the time."

The approach utilizes hybrid control algorithms to switch between models whose accuracy is normalized by their computational burden of predictive control methods. "This synergistic approach enables computationally aware cyber-physical systems, in which model accuracy can be jointly considered with computational requirements," says Sanfelice.

The grant, awarded by NSF as collaborative project between UC Santa Cruz and University of Arizona, is funded through the competitive Cyber-Physical Systems program.  More information about the award is available here.

About the Jack Baskin School of Engineering

The Baskin School of Engineering specializes in education and research across seven departments: applied mathematics and statistics, biomolecular engineering, computational media, computer engineering, computer science, electrical engineering and technology management.