Michael Otte talks about “Super-linear Parallel Path-Planning and the AnyCom idea” at MIT and iRobot

Michael Otte will give a talk about “Super-linear Parallel Path-Planning and the AnyCom idea” at iRobot and Emilio Frazzoli’s ARES lab at MIT on July 21st and 22nd, respectively.

Here are slides from the presentation

July 21, 11:00 am, iRobot (8 Crosby Drive, Bedford, MA)

July 22, 1:00 pm, MIT (Stata Center 32-d677) map: http://whereis.mit.edu/?go=32

Abstract:

The talk will be on recent advances in robotic path planning algorithms, with a focus on two recent results obtained during my PhD Thesis research in Correll Lab at the University of Colorado at Boulder.

I will start by introducing a new technique for distributed single-query path planning and demonstrate that it has super linear speedup on both multi-robot and manipulator problems. In other words, using a cluster of T computers gives a better result than 1 computer that is allowed to run T times as long. This also known as having parallelization efficiency greater than 1. Distributed algorithms with efficiencies greater than 1 are extremely rare; however, the proposed technique often achieves efficiencies greater than 2 and some as high as 9. To the best of my knowledge, the highest efficiency previously observed in this domain is 1.2. Theoretical results prove that the experimentally observed speed-up is the result of algorithmic design, and not simply a byproduct of more common hardware phenomena (e.g., better cache alignment). Moreover, analysis suggests that this result can be duplicated by applying our parallelization technique to any random tree algorithm that is expected to converge to an optimal solution given infinite time, and that operates in a configuration space obeying the triangle inequality.

The second half of the talk will show how the distributed path planning framework can be used by a team of robots to solve the centralized multi-robot path-planning problem. In this model the robotic team is formed into an ad-hoc distributed computing cluster using wireless Ethernet, such that the computational load of calculating a solution is distributed among all robots the solution will benefit. I use the term `Any-Com’ to describe the latter idea because each robot contributes to the global solution as much as communication reliability permits. The framework is probabilistically/resolution complete, and experiments are performed using the CU Prairiedog platform which is built on top of the iRobot Create.