IROS2019国际学术会议论文集 2125

Multirobot Charging Strategies A Game Theoretic Approach Tianshuang Gao1and Sourabh Bhattacharya2 Abstract This work considers the problem of assigning multiple robots to charging stations in order to minimize the total time required by all robots for the charging operation We fi rst show that the centralized problem is NP hard Then we formulate the charging problem as a non cooperative game We propose an algorithm to obtain the pure strategy Nash equilibrium of the non cooperative game and show its uniqueness We investigate the price of anarchy PoA of this equilibrium as a function of the number of robots and stations Next we leverage our analysis on static charging stations to propose strategies for reducing the total cost when the charging stations are mobile Finally we analyze the performance of the strategies proposed for the charging stations through extensive simulation I INTRODUCTION In the last decade multi robot systems have been exten sively deployed in civilian as well as in military applications 1 With the rapid advancement in sensing and computing technology the range of tasks performed by these robots has signifi cantly increased Multiple robots can perform tasks more effi ciently than a single robot and in some cases accomplish tasks that cannot be completed by a single robot Moreover distributed sensing and decision making increase the robustness of multi robot systems to failure compared to single robots Coordination of multiple robots to accomplish tasks remains an active area of research 2 However coor dination requires a reliable communication channel between robots to exchange information Establishing such a commu nication network in open environments over a wide area is a challenge due to the sheer cost and maintenance involved In this paper we explore a communication free technique for multirobot systems to complete tasks Specifi cally we investigate non cooperative charging strategies for a team of mobile robots For persistent operations robots rely on uninterrupted power supply When the on board power drops below a certain threshold the robot needs to abort its task and move towards a charging station to get charged Recharging facil ities for example rechargeable batteries and self recharge device or station are often deployed in order to provide power to the robots in the fi eld Current technology involves automated docking and battery swap systems 3 4 for recharging robots The time spent for the re charging task including traveling time and queuing time depends on the location of the charging stations relative to the robots In 1Tianshuang Gao is with Department Computer Science Iowa State University Ames IA 50011 USAtsgao iastate edu 2 Sourabh Bhattacharya is affi liated to the Department of Mechanical Engineering and the Department of Computer Science at Iowa State University Ames IA 50011 USAsbhattac iastate edu 5 the authors propose an algorithm that fi nds the minimum number of charging stations and their locations so that the robots can always reach a charging station from any location in the workspace without traveling more than a pre specifi ed number of steps However the queuing process is not consid ered when multiple robots are trying to recharge at a station In a centralized system a central authority can make a plan for the individual robots since the decision of the entire group has to be taken into account to minimize the wait time for any robot However determining the optimal plan for task allocation for a multirobot system MRS to maximize the expected overall system performance is typically an NP hard problem 6 It has been shown that the problem of persistent surveillance with energy and communication constraints is NP complete 7 in a centralized system and with the additional consideration of optimizing the total completion time the complexity of the problem further increases The problem considered in our work in centralized sce narios is related to job shop scheduling problem It has been proved that one machine job shop scheduling problem is NP hard problem 8 In 9 researchers studied job shop scheduling problem on a single machine and proposed an optimization algorithm called marriage in honey bees that can provide a near optimal solution In 10 the authors introduced a customized approximate dynamic programming to the online version of the problem where orders arrive at the system at random times For multiple machine job shop scheduling problem the authors in 11 developed several dominance properties and lower bounds for the problem of scheduling several independent jobs on multiple unrelated parallel machines with the objective of minimizing total tardiness Processing times of a job on different machines are different on unrelated parallel machine scheduling problems For identical parallel machines job scheduling problem the authors in 12 showed that the special case in which all jobs have equal processing times is solvable in polynomial time The problem considered in our work can be treated as an extension of a multiple machine job scheduling problem with the objective of minimizing total tardiness We investigate the problem of minimizing the sum of the total tardiness and the total traveling time Mobile robots deployed for outdoor applications generally rely on a decentralized communication architecture Apart from robustness a distinct advantage of decentralized com munication is the requirement of fewer data packets among robots for task completion This is especially benefi cial in environments where communication is unreliable due to poor infrastructure or presence of adversarial elements 13 In general decentralized strategies can either be cooperative IEEE Robotics and Automation Letters RAL paper presented at the 2019 IEEE RSJ International Conference on Intelligent Robots and Systems IROS Macau China November 4 8 2019 Copyright 2019 IEEE or non cooperative Cooperation arises in situations wherein multiple robots need to interact together to complete a task while increasing the total utility of the team 6 Alter natively cooperation is the interaction between the robots which work towards a common interest or reward 14 Non cooperation refers to a situation when robots act to fulfi ll their own self interest 15 In this case robots with confl icting utility functions compete with each other Each robot behaves selfi shly from a sociological point of view because a single robot wants to make decision motivated by self preservation In such scenarios a robot is unaware of the decision of other robots in the team However it may have information regarding their state for example relative position orientation or confi guration based on the sensor information In the past there has been some work related to charging mobile robotic platforms In 16 authors provide a near optimal recharging strategy on a self suffi cient robot boat For one robot and multiple stations the most effective strategy for the robot is to visit the closest station Our current work takes into account the waiting time incurred while being queued at a station In 17 the authors propose a strategy that does not require a robot to communicate but to compete for the resource They only consider the case of a single charging station In contrast our current work considers an arbitrary number of charging stations In 18 the authors investigate the problem of when to recharge and how long to recharge for multi robot systems They present a centralized solution which assumes robots communicate and share their states Our current work addresses the problem of multirobot charging in the absence of any communication network which renders a centralized solution inutile in such circumstances In 19 the authors address the problem of maintaining persistence in coordinated tasks performed by a team of autonomous robots employing a dedicated team of charging robots to service the team to sustain their operations over extended periods of time Unlike 19 our objective is to fi nd a near optimal allocation so that the total time spent in the recharging process for all robots is minimized In 20 the authors present a case study on three robots sharing a charging station with non direct communication The authors propose an experimental bottom up approach and three robots can remain in operation and effi ciently share a charging station using simple mechanisms The task of coming up with a sequence of actions that will achieve a goal is called planning 15 In 21 the authors propose a consensus based bundle algorithm that appropriately handles time windows of validity for tasks fuel costs of the vehicles and heterogeneity in the agent capabilities while preserving the robust convergence properties Although the authors proposed methodologies for handling disconnected network it still requires communication In 22 the authors proposed a distributed approach for a team of heterogeneous UAVs cooperating effi ciently in patrolling missions around irregular areas with low communication ranges and memory storage requirements In contradistinction our objective is to fi nd a planning solution for multiple robots and charging stations with communication constraints The main contributions of this work are as follows 1 In contradistinction to current approaches that formu late multirobot recharging problem as a multi vehicle routing problem 16 23 24 23 we formulate the problem as an optimal resource allocation problem We show that the optimal allocation of robots to charging stations that minimizes the total sum of traveling queueing and charging time for the entire team in a centralized setting is NP hard In a non cooperative setting that arises due to the lack of a communication network we present charging strategies for the robots that are in Nash equilibrium 2 Previous efforts in decentralized planning for recharg ing refueling in multirobot systems either rely on the presence of an underlying communication network 25 or assume only one charging station 17 Our work is the fi rst to propose non cooperative strategies for allocating a team of robots to multiple charging stations in the absence of a communication network 3 In this work we use the concept of price of anarchy PoA as a metric to evaluate the effi ciency of the proposed strategies Although researchers have pre viously used PoA in other engineering systems for example computer networks 26 internet 27 and transportation networks 28 our work is the fi rst to utilize it in the context of robotic networks The paper is organized as follows In Section II we present the problem formulation In Section III we show that the optimal solution to the recharging assignment problem in centralized scenarios is NP hard In Section IV we utilize a game theoretic approach to formalize the charging problem We propose an algorithm to compute the pure strategy Nash equilibrium of the game and prove its uniqueness In Section V we investigate the Price of Anarchy of the Nash Equilibrium In Section VI we consider the case of mobile charging stations In Section VII we present our conclusions II PROBLEMFORMULATION In this section we present the problem formulation Con sider n mobile robots R r1 r2 r3 rn located in a region We assume that each robot is equipped with sensors that can accurately provide the location of the other robots Consider a set of m identical charging stations S s1 s2 s3 sm located on the plane We assume that the charging stations are stationary and their location is known to all the robots Let tijdenote the traveling time of robot rion the shortest path to station sj Let tc i denote the recharging time for robot riat any charging station We assume that the charging time is the same for all robots at all stations This is a reasonable assumption since in the absence of any information about other robots except their location each robot can assume a worst case scenario in which other robots are fully discharged before they are being recharged at a station Let qijdenote the queuing time for robot riat station sj An allocation A of robots to stations is an injective mapping from R to S Let A Rm ndenote the set of all allocations of robots to the charging stations In a centralized scenario in which all the robots coordinate we defi ne the following cost function for an allocation A fc A n X i 1 tiA i qiA i tc i 1 The objective is to fi nd an optimal assignment A defi ned as follows A min A fc A 2 Intuitively when the on board power drops below a certain threshold for a robot it has to abort its task and get charged We want to reduce the time required for traveling and charging so that the robot is ready to resume its task at the earliest The objective function in 2 is the aggregate time spent by all the robots before they get fully recharged The problem in 2 is to fi nd the allocation for n robots to visit m charging stations that minimizes the total time required for traveling and charging for all the robots Since Pn i 1t c i is a constant that is independent of the allocation A fc in 2 can be redefi ned as follows fc A n X i 1 tiA i qij 3 In a non cooperative scenario each robot is assumed to be a selfi sh agent with its own payoff which depends on its action in this case the station it chooses Let Uidenote the action set of each robot which represents the set of stations that can be chosen by robot ri For our problem Ui S The cost incurred by robot riis given by the function Ji U R where U n 1Ui represents the joint action space of all players The elements of U are action profi les sj1 sjn where sjiis the station chosen by robot ri To put things in perspective an action profi le sj1 sjn corresponds to an allocation A where A i sji However unlike the centralized scenario each robot chooses its own station in a non cooperative setting Since the queing time for a robot also depends on the stations chosen by other robots let qi sj1 sjn denote the queing time of robot rifor an action profi le sj1 sjn Ji is defi ned as follows Ji sj1 sjn tiji qi sj1 sjn 4 Since the robots are assumed to be selfi sh the objective is to compute the action profi le s s j1 s jn which satisfi es the following Ji s Ji sji s ji i sji S 5 where s ji denotes the actions of all robots except riin the action profi le s Note In this work we consider a special case of the problem in which tc 1 tc 2 tc n tc We assume each robot can sense the location of the other robots without explicit communication However the station chosen by a robot is a private information which is not shared with other robots due to lack of a communication channel Additionally we assume that the nearest station associated to a robot is unique In reality a robot can break ties by giving priority to stations with lower indices Specifi cally if j k then the robot ri will take tij qij tik qik i R j k S as tij qij tik qik i R j k S III CENTRALIZEDALLOCATIONPROBLEM In this section we show that the centralized problem of allocating the charging stations to robots is NP hard First we describe the job shop scheduling problem of minimizing the tardiness on a single machine with arbitrary release dates In the job shop scheduling problem let n denote the number of jobs ridenote the release date or starting time of job i and Tidenote its tardiness in a schedule The objective is to fi nd a schedule minimizing Pn i 1Ti i e a beginning time tiand a completion time cifor each job i that minimizes the following objective n X i 1 Ti n X i 1 max ci di 0 n X i 1 max ti pi di 0 subject to ti riwhere piis the processing time of job i and diis its due time This problem is known to be NP hard if the job release dates are not identical 8 Theorem 1 The problem of fi nding the allocation A in 2 is NP hard Proof We show a reduction from the job shop scheduling problem of minimizing the total tardiness on a single machine with arbitrary release dates to our multi robot charging problem We construct an instance of our recharging problem from the job shop scheduling problem In our case the n jobs that need to be processed on a single machine represent n robots that need to get recharged in a single station The starting time of each job is ti which is equal to the time required by the robot to reach the station The processing time for each job pican be used to represent the recharging time of robot ri The due time of each job is ti pi which indicates the time at which ri will get fully charged Clearly we constructed a multiple robots recharging problem which is a special case when m 1 by using the job shop scheduling problem A solution to the job shop scheduling problem can be constructed in polynomial time using the optimal solution to the multi robot charging problem For this instance we can fi nd the solution of optimal total charging plus queuing time as long as we can fi nd the minimal tardiness in the job scheduling problem From the above analysis we conclude that the centralized problem of fi nding the optimal allocation is computationally intractable In the next section we adopt a game theoretic framework to fi nd the optimal allocation in non cooperative scenarios that arise due to lack of a communication network between the robots IV ALLOCATION AS A NON COOPERATIVE GAME Consider the following version of the charging problem under consideration which formulates it as a non cooperative game Assume that each robot behaves selfi shly and tries to minimize its own time required for getting fully charged Each robot can sense the location of the other robots However the station chosen by a robot is unknown to other robots due to the lack of a communication network Next we present an algorithm to calculate the pure strategy Nash equilibrium PSNE for the non cooperative game and show the uniqueness of the PSNE Then we show that the algorithm works for closed loop each robot takes into account the current position of other robots as well as open loop each robot only considers the initial position of the other robots information p