Multi-Robot Teamwork in Coverage, Patrolling, and Formation Maintenance.

We investigated specific tasks—multi-robot formation maintenance, coverage, and patrolling—to understand how teamwork can be useful in improving on the state of the art:

Formations

We departed from prior work using control theory to handle formation maintenance, devising optimal graph-theoretical algorithms instead. This resulted in significantly improving reliability of moving formations, and cut location errors by half.

Coverage

We developed various optimal, efficient, provably robust multi-robot coverage algorithms. These show, for example, that to minimize the coverage time, it might be necessary carry out redundant work.

Patrolling

We developed the first optimal, efficient, provably robust, multi-robot patrolling algorithms, for continuous areas and polylines. These distinguish two optimization criteria:

• Patrolling to optimize visit frequency (e.g., maximal visit uniformity), or
• Patrolling to optimize adversary capture likelihood, under different assumptions of the knowledge of the adversary.

Some of these have gone through a tech-transfer program with Israel’s leading defense contractors, e.g., Elbit and IAI, to patrol Israel’s borders.