Project Paper for 6.854 Members: Seungkook Yun ([email protected]) Sooho Park ([email protected]) Distributed Online Matching Algorithm For Multi-Path Planning of Mobile Robots 1. Introduction Currently, we are working on mobile robots which move only on a special structure: trusses (See Fig. 2). Each robot has two grippers and three joints for 3-d motion (See Fig.1). This robot is expected to move on the trusses and help construction of the structure in future. We need to develop a collaboration scheme for lots of robots on the same structure. Note that a robot can only move on the specific points on the trusses and every robot has the identical structure and functions. Also, it must occupy at least one point to support itself. Fig.1 the mobile robot and its structure: 3-joints and 2 grippers Fig.2 (a) truss structure and a robot (b) example of path planning of a single robot: numbers denote nodes on the trusses1.1 Problem Statement Our task is to deploy robots to request points on the trusses by minimum number of total moves. It is to minimize the energy usage. For this, we need a collision-free min-cost path planning algorithm for multi-robots since a robot can't move through the other robot. The trusses can be modeled by a graph, in which nodes are the specific points where a gripper of the robot can grasp and edges denote whether a robot can move between pairs of nodes. We will assume that the graph structure, the target points, and the initial position of robots are given, and also that the robots are collaborating. The real challenge is that we want a distributed algorithm. That is, we do not want a centralized controller which knows everything and controls all the robots. Instead, a robot has limited communication and sensing area which is modeled by number of edges from the node occupied by the robot, and it must decide which way to go with the limited (sensed) information. 1.2 Our Approach and Results In this paper, we show that the problem can be solved by a perfect matching between initial nodes and target nodes. The matching uses the fact that the robots are identical. This is not an offline matching problem, but closer to the online matching. However, this problem is different from the online matching in that a robot does not know how other robots are matched to the requests. From now, we call the problem ‘distributed online matching’. In the online matching, it is proven that the lower bound of the competitive ratio of any deterministic algorithm is (2k-1). The permutation algorithm [1] achieves this bound. In our work, a distributed matching algorithm is devised, using a greedy and the permutation algorithm. We prove that it has 21(3 )2kk− -competitive ratio for the case where each robot is deployed one by one, and 2(2 )kk−-competitive ratio for the simultaneous deployment. We also give a discussion about randomization, and conjecture that the randomization might not be helpful. 1.3 Clarification of the problem We clarify our problem as follows: y The truss structure is modeled by an undirected graph G, where nodes are points where a robot can grasp and there is a positive cost on each edge. y Naturally, triangular inequality holds for G y We model each robot as a point on the graph G y The number of the robots is k, and all robots are identical y The sensing range of robots is assumed to be one, i.e. a robot can communicate with other robot if and only if they are adjacent. y When the communication is possible, the robots can share all information they have. y Initially, each robot is located in ri, and R is a set of all the initial nodes.y All the target nodes are given to each robot. T is a set of the target nodes. tj denotes each target node. Note that j is not related with index of robots. T can be overlapped with R. y The goal is for the robots to reach all target nodes with minimum cost. This paper is organized as follows: Section 2 describes the best offline algorithm and how it can be viewed as the matching problem. In Section 3, we propose the distributed online matching algorithm and show how it works. We give discussions about the bound in section 4. We will give some modification to the algorithm at Section 5 to improve the practicality of the algorithm. 2. Optimal offline algorithm In this section, we discuss about the optimum solution of the centralized offline case where a central controller knows everything on the graph and control each robot. We also show that we can solve the problem with a perfect matching algorithm. 2.1 Optimal solution for the centralized offline case This problem can be reduced to a min-cost disjoint path problem with vertex capacities since at any time each vertex can be occupied by only one robot. We solve this problem as follows: - Expand the graph G to reflect the vertex capacities (as we solved in the problem set). Note that vertex capacity is one for all vertices. - Find disjoint paths of the expanded graph. In our case, we should use min-cost max flow rather than just max flow algorithm. This yields the min cost paths without any collision. 2.2 Can this be solved as a matching problem? If a robot does not have its physical size, any perfect matching between R and T will give a feasible solution, and each robot can move on the shortest path to its matched target node. Moreover, the min-cost perfect matching is, of course, the optimum solution. However, in a real system, this set of the shortest paths may raise two critical problems: the collision where robots' path cross and the deadlock where paths form a cycle in the graph. Now we propose an intuitive selection criterion to avoid these two issues. 2.2.1 Selection criteria: to exchange identities When two paths cross, simply changing identities, which means to exchange all information they have and the action they are executing now, will prevent the collision as shown in Fig. 3. On the other case when adjacent robots shares the same edge but their paths do not cross, let the higher ID robots go first and the other robots wait until robots with the higher ID pass the edge.r1r2p1p2r1r2p1p2 (a) (b) Fig. 3 exchanging identities (a) two paths are crossing (b) after exchanging IDs 2.2.2 Selection criteria: to break a deadlock A deadlock is the status in which some robots can not move even though any paths of the robots are not crossed as shown in Fig. 4. There are four robots {r1, r2, r3, r4} with each path {p1,