IROS2019国际学术会议论文集 2576

A Deep Learning Approach for Probabilistic Security in Multi Robot Teams Remy Wehbe and Ryan K Williams Abstract In this paper we train a convolutional neural network CNN to predict the probability of security of a multi robot system MRS when robot interactions are probabilistic In the context of MRSs probabilistic security is defi ned using the control theoretic notion of left invertibility a necessary and suffi cient condition to avoid perfect attacks As the probabilistic security problem is NP Complete current solutions fail to generalize as the size of the MRS increases Fortunately deep neural networks have shown promising results in the effi cient computation of solutions to hard problems which motivates our CNN based approach In this context formulating a method for data generation is non trivial due to the large space of available interaction graph topologies and training biases introduced by random sampling As such we use a two step approach for data generation where we fi rst explore the space of available topologies then populate the sampled topologies with probabil ity distributions all while preventing any biases from occurring in the data We then train a CNN with convolution layers specifi cally tailored for graph adjacency matrices Finally the validity of our results is demonstrated through simulations I INTRODUCTION In recent years research in multi robot systems MRSs has garnered much attention due to their applicability to a wide range of tasks such as search and rescue missions collecting data to improve agriculture conducting routine surveillance etc 1 An MRS has several advantages over a single robot system in the form of robustness the potential to recover and adapt to failure versatility the ability to integrate new robots into the system and adaptability the usage of the same robot in different MRSs Unfortunately some of the aspects that make an MRS so compelling introduce an added layer of complexity For example an MRS is only as good as the coordination between its robots which is often diffi cult to achieve in practice A related challenge is the MRS s dependence on communication which is affected by noise and disturbances in the environment A third challenge which is the focus of this paper is the threat of malicious attackers who aim to disrupt nominal operation The distributed nature of MRSs make them vulnerable to a variety of attacks which include exploiting an MRS s com munication using a denial of service attack 2 attempting to manipulate the control law by using either a false data injection 3 or replay attack 4 or having unreliable agents bias nominal operation by sending false information 5 This has necessitated the design of secure and resilient MRSs The fi rst such work goes back to 6 which tackles the problem of agreeing on a message sent by a Byzantine General R Wehbe and R K Williams are with the Department of Electrical and Computer Engineering Virginia Polytechnic Institute and State University Blacksburg VA USA E mail rewehbe rywilli1 vt edu Since then works such as 5 have derived control and graph theoretic conditions to ensure consensus in the presence of unreliable agents Similarly 7 introduced the W MSR algorithm which allows an MRS to achieve consensus using only local information given that it satisfi es the connectivity conditions of r s robustness 8 extends the previous work to the SW MSR algorithm which guarantees the consensus of time varying networks with dynamic agents 9 introduced a resilient formation control algorithm for mobile robots to achieve consensus in the presence of attackers Additionally 10 derived graph theoretic conditions for MRSs to avoid perfect attacks attacks that affect the MRS s state without affecting its measurements Most of the recent literature focuses on MRSs with deter ministic interactions However because of the distributed na ture of an MRS communication can be affected by external interference as well as adversarial attacks such as jamming As such modeling an MRS s interactions as probabilistic allows us to incorporate disturbance attacks into the commu nication model In this paper we leverage the results of 10 where it is assumed that adversaries are attempting to carry out a perfect attack which disrupts the system s dynamics without being detected by a centralized detector that can impose countermeasures To this end the authors present graph theoretic conditions for an MRS to avoid perfect attacks As an extension we defi ne the probabilistic security problem as the probability that an MRS can avoid perfect attacks given that robot interactions are probabilistic In our previous work 11 12 we tackle the probabilistic MRS security problem using binary decision diagrams BDDs 13 The diffi culty faced in 11 12 is that solving for the probability of security is NP Complete and thus a sequential algorithm does not scale well with the size of the MRS and is diffi cult to execute in real time The inspiration for the present work is the tremendous success deep learning has shown in fi nding approximate solutions for notoriously diffi cult problems such as the games of Go and Chess 14 and the traveling salesman problem 15 Additionally MRSs have seen the use of machine learning approaches in tasks such as multi agent predictive modeling 16 and robustness detection 17 Finally several new deep learning approaches have been specifi cally developed to operate on graphs as summarized in 18 All of this recent evidence leads us to investigate the application of deep neural networks to the probabilistic multi robot security problem In this paper we develop a deep learning approach based on CNNs to approximate the probability that an MRS is secure from perfect attacks As mentioned previously 11 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 12 solve an NP Complete problem and are thus limited to small MRSs In this work we target medium to large MRSs that were only solvable using computationally expensive Monte Carlo simulations However data generation is non trivial because the space of weighted graphs is infi nite and random sampling introduces signifi cant biases As such we develop a two stage process where we fi rst perform a targeted exploration of the space of available topologies then populate the topologies with probability distributions without introducing any signifi cant biases into our data set Next we employ convolution layers specifi cally adapted to operate on graph adjacency matrices to create a CNN capable of estimating the probability of security of an MRS Finally we demonstrate the validity of our approach through simulations II PRELIMINARIES A Modeling Robots and their Interactions An MRS is formed of n robots from the set Ir 1 2 n Each robot can be observed by one of m observers from the set Io 1 2 m where the number of observers cannot exceed the number of robots n m Robots send their state to their observers and neigh boring robots through a communication sensing network represented by a directed graph Specifi cally we model deterministic interactions as a digraph G V E where robots and observers are represented by the set of vertices V v1 v2 vn m while interactions communica tion sensing are represented using the set of edges E eij vi vj V Denote by A R n m n m the adjacency matrix of G V E with Aij 1 if eij E and Aij 0 otherwise Denote by dothe out degree of a vertex and dithe in degree of a vertex To model robot to robot interactions we will exploit prob abilistic graphs where edge existence is associated with random variables described by some probability distribution A probabilistic graph G V E has a deterministic vertex set V v1 v2 vn m representing robots and observers and a probabilistic edge set E eij vi vj V rep resenting interactions Each edge eij E has a probability of existence Pij and edges are assumed to be independent i e P eij ekl P eij P ekl Our interpretation for this paper is that at each time instant t R 0 the probabilistic graph G takes one of the 2 n m 2 E possible realizations As a result the system operates over a sequence of graphs G V E realized at every time t with V V and E E As such the adjacency matrix A will be replaced by a probabilistic adjacency matrix A a weighted adjacency where Aij Pijif eij E and Aij 0 otherwise B Attack Model and Conditions for Network Security As previously mentioned we adopt the control theoretic attack model and the graph theoretic security conditions developed by 10 to guarantee a system can avoid perfect attacks Each robot i Iris associated with a scalar state xi t R and each observer j Iomeasures a scalar state yj t R Defi ne x t x1 t x2 t xn t Rnas a Fig 1 Probabilistic interaction graph of an MRS with robots represented by blue observers by green attackers by black and node o by red 11 stacked vector of xi t and y t y1 t y2 t ym t Rmas a stacked vector of yj t It is assumed that each observer can measure the state of only one robot then the robots control law under adversarial attacks becomes xa t 1 Axa t Baua t w t 1 ya t Cxa t Daua t 2 where the terms ua t and w t represent stacked vectors of malicious inputs and process noise respectively Setting ua t 0 results in the dynamics of the states that we wish to secure under nominal conditions State estimation is done by a centralized detector using a linear fi lter An attack is assumed perfect if an attacker can maintain z t z t za t 0 while ua t 6 0 where z t and za t are the nominal and attack fi lter residuals Let p m be the number of malicious agents attackers in a system Then a graph theoretic condition ensuring an MRS is not perfectly attackable secure in a control theoretic manner is given by Theorem 1 10 Graph theoretic Security Asystem A C is structurally left invertible i e secure for all feasible sets of malicious agents if and only if for each robot i Ir the minimum size of a vertex separator between robot i and the node o satisfi es Si p In the above result o is a newly added vertex with incom ing directed edges from all observers Figure 1 and Si is the minimum number of nodes whose removal disconnects robot i from o C Probabilistic Multi Robot Security Theorem 1 can only be used on graphs of the form G V E to evaluate a system s deterministic security In 11 we tackle the more general problem of calculating the probability of security of an MRS denoted by Psecure for graphs of the form G V E Calculating Psecurerequires the enumeration of the set of all possible disjoint paths of size p from each robot i to o denoted by Rp i Then Psecure can be calculated using the following theorem Theorem 2 11 Probabilistic Security The probabil ity that system A C is structurally left invertible i e secure for all feasible sets of malicious nodes p is equal to the probability of the conjunction of Rp i i Ir where Rp i is calculated using the disjunction of all the events Hp i l Rp i That is Psecure P n i 1 Rp i l 1 p Y 1 3 where Hp i l is the lthdisjoint path in the set Rp i H p i l p Q 1 with e1 e2 e representing the s path in Hp i l Solving 3 requires the use of BDDs see 11 Additionally an approximation of this problem can be found in 12 III PROBLEMFORMULATION It was shown in 11 that solving 3 is at least NP Complete which makes this problem intractable for medium to large scale MRSs The presented solution was based on binary decision diagrams BDDs and the enumeration of the entire disjoint path space Rp i i Ir However BDDs suffer from an exponential growth in the number of edges having a worst case complexity of O 2 E and the problem of enumerating the entire space Rp i i Iris P complete 19 12 mitigates the complexity of the problem by opting to fi nd an approximation for 3 Briefl y an optimization problem is formulated to obtain a fi xed cardinality set R p i which maximizes the estimate of Psecure Although this approach eliminates the P complete enumeration task the general problem is still intractable because 12 uses BDDs to solve for the approximation The only other alternative for a medium to large MRS seeking to calculate Psecureis to use Monte Carlo MC simulation Instead of exploiting MC directly we will leverage MC in the generation of training data to yield a CNN that can achieve real time inference for the probabilistic security problem To begin we briefl y outline an MC approach to the probabilistic security problem Denote by PMCthe estimate of Psecurebased on Monte Carlo Simulations To calculate PMCfor a probabilistic graph G V E we have to take deterministic realizations of the graph by setting every edge eij A to either 0 or 1 based on its probability Pij Then for each G V E realization the conditions of Theorem 1 are checked According to Menger s Theorem 20 Si is equal to the maximum number of node disjoint paths from i to o As such Si can be obtained by solving a 0 1 max fl ow min cut problem using the Ford Fulkerson FF algorithm 21 applied to an enlarged adjacency matrix Ae FF applied to A results in the maximum number of edge disjoint paths The enlarged adjacency matrix is obtained by splitting every node vi G V E into two nodes v1 i v2i connecting v1i to v2 i by a directed edge and redirecting all incoming edges of vi to v1 i and all outgoing edges of vito v2 i Denote by secthe number of deterministic graphs that are secure and denote by totalthe total number of deterministic realizations used for the MC Then an estimate of Psecureis calculated using PMC sec total 4 The accuracy of PMCdepends on the number of realiza tions used with PMCconverging to Psecureas total The per robot complexity of the Ford Fulkerson algorithm is polynomial given by O Ef 20 where f is the maximum fl ow in the graph This MC approach is suited for static graphs that do not require fast updates of security Unfortu nately MRSs are dynamic in nature which adds complexity since A may change at every time instant To this end we present a deep learning approach based on CNNs to estimate the probability of security of an MRS Our main motivation comes from our knowledge that solving 3 results in a single function in the form of a BDD that can calculate Psecure for all possible graphs with a fi xed number of robots and attackers regardless of topology probability distribution As such we aim to train a CNN using an unbiased data set obtained by exploring the uncountably infi nite space of probabilistic graphs which allows our CNN to converge to the desired function while avoiding overfi tting that can result from biased data sets IV DATAGENERATION The quality and quantity of data are the key concerns in the application of deep neural networks at the state of the art Unfortunately unlike typical deep learning problems such as image classifi cation there are no standard data sets for our problem This motivates us to present a data sampling algorithm for the probabilistic security problem First let us describe the ideal composition of our data set By looking at the security conditions of Theorem 2 it is apparent that Psecuredepends on the topology and edge probabilities of the interaction graph Then it is only natural to use the probabilistic adjacency matrix A as an input to our CNN and seek Psecureas an output Unfortunately the exact value of Psecuremust be computed from 3 which is intractable for the systems we are considering Instead we use an estimate of Psecurebased on PMC and thus the quality of data can be tuned by modifying the total MC samples To sample data one may use prior knowledge of the MRS s behaviour Though care has to be taken when training CNN models on specifi cally sampled data because overfi tting may prevent the CNN from generalizing if the MRS deviates from the expected behavior With that in mind we propose a data generation method that allows the user to generate both specifi c and general data sets by controlling the space of explored topologies and probability distributions In this context a general data set is one sampled by exploring the uncountably infi nite space of probabilistic adjacency matrices and reaching relevant parts of the space while limiting the samples taken This allows us to train CNNs that are robust to changes in the topology and or probability distribution of an MRS Attempting to uniformly randomly generate data may be relevant for specifi c data sets with fi xed probability distributions However randomly generating a data set introduces a lot of bias into the system as every deterministic adjacency matrix A has to be populated with a compatible probability distribution 2 Otherwise in our experience the data set will be biased with the majority of PMCvalues near either zero or one In this section we will detail the two main steps required to generate the data set denoted by S A1 A2 A S First the structure topology A of the graph is generated then A is populated with edges having a given probability distribution to obtain A We remind the reader that adjacency matrices are directed and p is the number of attackers A Topology Generation A graph s topology is solely responsible for determining whether Psecure 0 or Psecure 0 regardless of the edge probability distribution This is a direct result of Theorem 1 Thus topology generation will be split between T0 A1 0 A20 A T0 0 and Tnz A1 nz A2nz A Tnz nz which are defi ned as sets of adjacency matrices satisfying Psecure 0 and Psecure 0 respectively First we start by obtaining bounds on the number of edges that are allowed to exist in the adjacency matrices These bounds are calculated based on proper interpretations of Theorem 1 For example a fully connected graph having m p will always have a Psecure 0 and should not be generated as part of T0 For A0 T0 the minimum number of edges that can exist Elb 0 is trivially obtained as Elb0 0 since a graph with no edges cannot be secure Corollary 1 The upper bound on the number of edges is given by