Distributed Autonomous Robotic Systems 7
The goalof the 8th Symposium on Distributed Autonomous Robotic Systems (DARS) is to exchange and stimulate research ideas to realize advanced d- tributed robotic systems. Technologies, algorithms, and system architectures will be presented and discussed d
- PDF / 7,549,251 Bytes
- 261 Pages / 436 x 663 pts Page_size
- 46 Downloads / 229 Views
0DULD*LQL5LFKDUG9R\OHV (GV
'LVWULEXWHG$XWRQRPRXV 5RERWLF6\VWHPV
:LWK)LJXUHV
ABC
0DULD*LQL &RPSXWHU6FLHQFH (QJLQHHULQJ 8QLYHUVLW\RI0LQQHVRWD8QLRQ6W6( URRP 0LQHDSROLV0186$ 5LFKDUG9R\OHV &RPSXWHU6FLHQFH (QJLQHHULQJ 8QLYHUVLW\RI0LQQHVRWD8QLRQ6W6( URRP 0LQHDSROLV0186$
/LEUDU\RI&RQJUHVV&RQWURO1XPEHU ,6%16SULQJHU9HUODJ7RN\R%HUOLQ+HLGHOEHUJ1HZ 1 (Algorithm 4), if both Sj and Sk are empty, the IDs will not be added to DCRR , also recall that there is no duplicate IDs in messages, because no robot stamps a message that it has previously stamped. The two internally vertex-disjoint paths between v1 and v2 are v1 Sj v2 and v1 Sk v2 . Thus v1 and v2 are doubly-connected. Similar to the argument at the end of Section 1.3.1, after nc seconds no message remains in the system, and the algorithm terminates. 1.3.3 Biconnectivity Check After running CR - FILL and DCR - FILL consecutively, the CR and DCR lists will be accurate. Notice that both algorithms for filling the CR and DCR lists finish within a known time limit. Thus the robots should wait 3N c seconds, and afterwards CR and DCR lists will be accurate. For robot r if CRr and DCRr are equal, it means that r is doubly-connected to all the robots that it is connected to. By Theorem 1, we know if there are two robots r1 and r2 that are doubly-connected to all other robots, then the robot graph is biconnected. Also, we know by Lemma 1 that if there is a robot that is not doubly-connected to all other robots, the robot graph is not biconnected. Thus if the robot and one of its neighbors is doubly-connected to all other robots, the robot knows that the robot graph is biconnected. Also if the robot or one of its neighbors is not doubly-connected to all other robots, it will know that the robot graph is not biconnected. The overview of the biconnectivity check algorithm is shown in Algorithm 5. The initiator robot (which can be any robot who wants to check biconnectivity) starts by sending a (“CHECK - REQUEST”,()) message to its neighbors to ask them to check if they are doubly-connected to other robots or not. Upon receiving a (“CHECK REQUEST ”,()) the other robots run biconnectivity check (unless they are already running it) as non-initiators (skipping line 3 of Algorithm 5). Note that multiple robots can run the biconnectivity check algorithm in parallel.
8
Mazda Ahmadi and Peter Stone
If the robot is doubly-connected to all other robots, it sends the message (“DC ()) to all its neighbor robots, and a (“DC - FALSE”,()) message otherwise. If the robot is doubly-connected to all other robots and receives a (“DC - TRUE”, ()) message, it knows that the robot graph is biconnected. Otherwise (if it is not biconnected to all other robots, or receives a (“DC - FALSE”, ()) message) it knows that the robot graph is not biconnected. Since the initiator and its neighbors should run the biconnectivity check, the total time needed for the biconnectivity check to complete i
Data Loading...
