Title :
Multi-UGV multi-destination navigation in coordinate-free and localization-free Wireless Sensor and Actuator Networks
Author :
Guyu Zhang ; Selmic, Rastko R. ; Duncan, Christian A. ; Kanno, Jinko
Author_Institution :
Electr. Eng. Dept., Louisiana Tech Univ., Ruston, LA, USA
Abstract :
New Unmanned Ground Vehicle (UGV) navigation algorithms in coordinate-free and localization-free Wireless Sensor and Actuator Networks (WSANs) are presented. The algorithms are distributed and designed for multi-UGV multi-destination navigation in a sensor network environment. The proposed method eliminates possible multiplicity of destination nodes. A Leader Election Algorithm is used to uniquely identify destination nodes, followed by a Hop-distance Assignment Algorithm where each node stores hop-distances from all destinations. The multi-UGV multi-destination navigation planning problem is formulated as a task allocation problem, where each UGV is considered as an agent and each destination as a task. Since even in the special case of a single UGV navigation, the problem, being similar to the well-known Traveling Salesman Problem, is NP-complete, an allocation algorithm that is suboptimal with respect to the total traveled distance is presented. A communication complexity analysis is provided. Both experimental and simulation results are presented to illustrate the effectiveness of the proposed navigation method.
Keywords :
actuators; computational complexity; mobile robots; multi-robot systems; path planning; remotely operated vehicles; wireless sensor networks; NP-complete problem; WSAN; communication complexity analysis; coordinate-free wireless sensor and actuator networks; destination nodes; hop-distance assignment algorithm; leader election algorithm; localization-free wireless sensor and actuator networks; multiUGV multidestination navigation; navigation planning problem; sensor network environment; task allocation problem; traveling salesman problem; unmanned ground vehicles; Algorithm design and analysis; Electronic mail; Lead; Navigation; Nominations and elections; Unmanned ground vehicle navigation; task allocation problem; wireless sensor and actuator networks;
Conference_Titel :
Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on
Conference_Location :
Firenze
Print_ISBN :
978-1-4673-5714-2
DOI :
10.1109/CDC.2013.6760523