2016-06-29: Autonomy Incubator Develops Collision Detection Capabilities

Javier updates fellow intern Kastan Day on his research.

This is intern Javier Puig Navarro's third summer at the Autonomy Incubator (Ai), and he's wasted no time in churning out his typical extraordinary, innovative avionics research. When he pulled me aside to show me his work after lunch today, I was expecting to be amazed as usual, but something about today seemed different.

"I just thought you might like to see it," he said. "It's very pretty."

"Pretty?" I asked. Avionics is cool for a lot of reasons; aesthetics usually isn't one of them. But, heck, he was right. Look at this.

The graph model from Javier's algorithm.

One of Javier's many good qualities is that he's an excellent teacher (as many of the younger interns can attest), so I actually understand what's going on here enough to explain it to you. Ready? 

The algorithm Javier created is a collision detection algorithm for autonomous vehicles. It looks at the planned path for the vehicle compared to other obstacles and vehicles in the area, and determines if a crash is going to happen. 

"Collision checking can be used in the planning phase, but also on-line—if it's very efficient—for path re-planning and obstacle avoidance," he said. "Basically, what it does is tell you if two entities collide."

That's easy enough to understand, right? It's the way he does it that's the really cool part, and what generates all these trippy graphs.

The red and green shapes on the right are two randomly generated shapes, which may or may not intersect. Imagine they're two UAVs, and intersecting means they're colliding. The blue shape on the left is the Minkowski Addition, which is very much beyond my realm of understanding (here's a PowerPoint if you're into math) but can be understood as the "sum" of the two shapes. If the red and green shapes intersect, then the origin of the Minkowski Addition will be inside the blue shape. If the red and green shapes do not intersect, then the origin will be outside the blue shape. Here, let's switch to 2D so this is easier to see.

The red and green shapes intersect, so the origin (the black dot) is inside the Minkowski addition. The algorithm needs to confirm that the origin is inside the shape in order to determine that there's been a collision. How does it do this? More math!

The algorithm picks a random vertex of the blue shape (vertex A) and draws a line to the vertex that would put the line closest to the origin (vertex B). Javier used the GJK Distance Algorithm to let his program do this, which is again out of my wheelhouse, but here's the paper if you're interested.

Then, it looks for a point that would make a perpendicular line to the line between A and B, again in the direction of the origin. 

"The idea is that you always expand in the direction of the origin," Javier said.

Once the algorithm creates a shape that encompasses the origin, it knows that a collision has happened and sends out an alert. If the origin can't be encompassed, then the algorithm knows it must be outside of the shape and sends a "no collision" message. It can usually do this in less than six iterations, which is really, really fast.

"We do not need to compute all these vertices," Javier said, gesturing at the blue shape on the screen. The algorithm is iterative, which means it's starts at one point and keeps drawing shapes until it finds a solution. It does the minimum amount of work necessary to get the right answer, and then stops. This kind of agility will be crucial once Javier's algorithm gets implemented in real-time on a UAV. For now, he's also exploring other applications of his work.

"Now, the conclusion is collision or no collision. Then you could modify this algorithm to get the minimum distance between points and the penetration distance," he said.