Pick-Up and Delivery Planning in Multi-Agent Systems under Temporal Logic Specications

Abstract: This thesis describes an approach for solving planning problems for a team of robots involving picking up and moving objects. The temporal goals are described using linear temporal logic over subsets of the workspace. Temporal logic is a convenient formalism to capture the usual control specications such as reachability and invariance as well as more complex specications like sequencing and obstacle avoidance. Those goals include the positions of the robots and the positions of the objects, e.g, go to a given location, bring an object there or pick up this object. We consider robots moving in a 2D environment which is partitioned into non-overlapping regions. A cost representing the total number of actions done by all the robots will be used to evaluate the quality of the runs. Our goal is to create a plan in a decentralized way for the robots that has a small cost and makes the robots collaborate to decrease the cost even more. The approach is divided in several steps. First a plan is created for each robot using an abstraction of the robot and its specication. This plan describes the sequence of abstract actions the robot will do to full its specifications. Second those actions are ordered in order to make their global cost as small as possible. Third and nally, the robot path for executing each action is found using automata theory. Such path is guaranteed to respect the global specication of the robot. We support the proposed theory with experimental results, showing that it gives an optimal solution in some simple examples.