Employing Concurrency for Faster Computation in CLASS

The need for speed

One key premise of the CLASS project is real-time computation - the ability to do computation efficiently, as close to the rate of data generation as possible. Understandably, this imposes restrictions on the business logic of the application, but more importantly, it requires that the CLASS software stack deploys the business logic as efficiently as possible while leveraging all hardware assets. One key hardware asset, especially in CLASS, is that of compute concurrency - multiplicity of computing resources and memory distributed over multiple machines in the compute continuum. In this blog, we present how we implement key stages of one of the most challenging latency-sensitive workflows in CLASS use-case - the obstacle avoidance workflow.

Challenging obstacles ahead

Figure 1: Warning Area vs. Safety Area

The CLASS use-case of obstacle avoidance involves notifying drivers of “connected cars” (cars capable of receiving notifications) of potential future collisions with obstacles. Many modern connected cars already carry some early-warning collision sensors, such as LIDARs and Radars. So, you would wonder - what value does CLASS add? And the answer is - for those obstacles beyond the sensing range of the car. Let’s say you are turning right, and somebody is starting to cross the street just behind the corner. Or, maybe you are driving backwards, and a bicycle rider pops up behind a parked car near you. In all these cases and many others, your car sensors will not be able to see through the objects that surround your car to detect the imminent collision. CLASS leverages stationary urban sensors, such as smart cameras, and mobile sensors of other cars in the urban arena, to extend the awareness of each car driver into a much larger warning area (as opposed to the safety area defined by the car’s sensors), as shown in Figure 1, thereby making road traffic much safer.

How does it work? Basically, it is all about crunching data. Fast. Cameras scan an urban arena, such as a street, or an intersection. The cameras video feed is converted in real-time to symbolic anonymized representations of objects - pedestrians, cars, trucks, bicycles, etc. Over a period of time, each object’s recorded locations become a history of the object’s movement, upon which we can reasonably predict near-future movement (especially for machines – bicycles and heavier). This is called Trajectory Prediction (TP). Based on the predicted trajectories of two objects, CLASS can detect probable near-future collisions between the objects – this is called Collision Detection (CD). In CLASS, we apply CD only to connected cars and objects in their respective warning area. If a potential collision is detected, the car is notified. Figure 2 sums it all.

Figure 2: Obstacle avoidance workflow

Maps will show the way

As shown above, there are a lot of computations to be done on lots of data, and quickly. For cars travelling at urban speed limit of 50 Km/h, it is only a matter of few seconds at best until they hit objects within range of tens of meters. And there are many cars and many more objects to process.

Note that all TP computations are independent, in the sense that each object has its own trajectory computed based on its own data, independently of others. Similarly, for CD, each object pair has all the data it needs to do the computation, independently of other objects. Also, determining for two given objects if one is in the warning area of the other is a geometrical computation that depends only on the objects’ data. Last, object updates are injected to the CLASS application in snapshots, each one updating multiple objects together, because each video analysis iteration results in identifying multiple objects in video frames.

Based on the above observations, we consider map/reduce [1] to be an efficient way to execute TP and CD in a timely manner, leveraging concurrent execution across cores and machines in the CLASS compute continuum. Generally speaking, map(f, D) is an operation of applying the function f() independently to each element of the dataset D. So, in CLASS, we can define TP as: TP(S)=map(tp,S) where S is a snapshot of new or updated objects and tp() is the function of computing trajectory for a single object. For CD, it’s a little more interesting, since CD is a binary function that further needs to be applied subject to filtering by warning area: CD(CC,O)=map(f,CC×O), where CC is a subset of connected cars and O is a subset of CLASS street objects that are “nearby” the connected cars, selected through geohash [2] proximity. Thus, f() can be defined as: f(cc,o)=if wa(cc,o)  then cd(cc,o), where wa(cc, o) is a predicate function that determines if object o is in the warning area if cc and cd() is the actual collision detection algorithm that checks for possible collision between objects based on the predicted trajectories of both objects.

In CLASS, we employ the Lithops [3] (formerly known as PyWren) framework as a lightweight implementation of map/reduce over the OpenWhisk [4]  serverless platform which at the heart of CLASS analytics [5]. Beyond the enablement of concurrent computation, running on serverless allows releasing resources when not needed, which is important in constrained environments such as edge nodes. The integration of Lithops and dataClay contributed by CLASS [6] allows TP and CD to be retrieve their input data dynamically from dataClay, anywhere in the continuum. Last, TP and CD can be packaged as serverless functions to be invoked from a workflow or by events.

Conclusions

Efficient processing of large amounts of data is critical in CLASS, especially in time-limited use-cases such as obstacle avoidance. In this blog we have reviewed this interesting use-case and explained how we employ concurrency to process CLASS object data for trajectory prediction and collision detection, which are key computation stages of collision detection. We find this work to be quite interesting, and even more so - potentially helpful in improving the quality of future urban life.

References

[1]     Wikipedia Community, "MapReduce - Wikipedia," [Online]. Available: https://en.wikipedia.org/wiki/MapReduce.
[2]     Wikipedia Community, "Geohash - wikipedia," [Online]. Available: https://en.wikipedia.org/wiki/Geohash. [Accessed November 2020].
[3]     Lithops Community, "Lithops - Lightweight Optimized Processing," [Online]. Available: https://github.com/lithops-cloud/lithops. [Accessed June 2020].
[4]     OpenWhisk Community, "Apache OpenWhisk package that can be used to create periodic, time-based alarms," [Online]. Available: https://github.com/apache/incubator-openwhisk-package-alarms. [Accessed 3 2019].
[5]     E. Hadad and S. Jbara, " Using OpenWhisk as a Polyglot Real-Time Event-Driven Programming Model in CLASS," 2018. [Online]. Available: https://class-project.eu/news/using-openwhisk-polyglot-real-time-event-driven-programming-model-class.
[6]     E. Hadad and S. Jbara, "Boosting Big Data Developer Productivity with PyWren and DataClay," [Online]. Available: https://class-project.eu/news/boosting-big-data-developer-productivity-pywren-and-dataclay.