Decision Making as Optimization in Multi-robot Teams

Abstract.
A key challenge in multi-robot teaming research in determining how to properly enable robots to make decisions on actions they should take to contribute to the overall system objective. This article discusses how many form of decision making in multi robot teams can be formulated as optimization problems. In particular, we examine the common multi-robot capabilities of task allocation, path planning, formation generation, and target tracking/observation, showing how each can be represented as optimization problems. Of course, global optimization solutions to such formulations are not possible, as it is well known that such problems are intractable. However,many researchers have successfully built solutions that are approximations to the global problems, which work well in practice. While we do not argue that all decision making in multi-robot systems should be based on optimization formulations, it is instructive to study when this technique is appropriate. Future development of new approximation algorithms to well-known global optimization problems can therefore have an important positive impact for many applications in multi-robot systems.