How we beat the state of the art in a week

How we beat the state of the art in a week

At Shadow, we’re focusing on making complex robots intuitive to use. For that we need very good path planning. There are plenty of amazing solutions out there, but we were recently faced with a project where those state of the art solutions just weren’t good enough for us. We needed a super fast planner that generated trajectories that “looked good”.

So we decided to tackle the problem ourselves, but those libraries have been a long time in development, with loads of talented people working on them. So how can we actually beat that? And in a very short time — one week — thanks to the looming project deadline?

Don’t panic

The first natural answer is to freak out. It won’t be possible to beat the existing solutions in such a short time in a relatively complex field. But what I always keep in mind is that we don’t need a beautiful generic solution. We need a solution that’s tailored to our need.

This means that the solution will probably not work outside of the constraints we set, but it should work perfectly inside those.

Simplify

Let’s consider the case of a robot picking items up from a table. If we look at the problem, we know that there’s always going to be free space above the objects. Obviously it’s a huge constraint to place on our environment, but it simplifies the problem drastically.

All the space above the table or the obstacles is free

Now that we have this limitation on our environment, a trivial solution can be implemented quickly and efficiently:

  • compute the point that’s one step closer to the goal from where we are
Computing next step 

  • if that next point is in collision then move up until there’s no collision anymore
Going above the obstacle for a given step 

  • iterate until you reach the goal.
Final plan

Final words

By simplifying our problem drastically and looking for a narrow solution instead of a generic one, we were able to get extremely good results and match our deadline. Our planner has obviously a few more tricks up its sleeve but the logic above is a good simplification. With a bit more work, the plan can easily be made smoother.

A plan that took 8ms to generate

I’m fully aware that this approach of simplifying problems cannot always be applied, especially to robots deployed in unconstrained environments. But in my opinion it’s crucial to always keep this process in mind!

We’d love to hear your thoughts! Make sure you @shadowrobot and also @ugocupcic (our Chief Technical Architect, who wrote this article!).