Research On Utilizing Complex Network Attributes For Distributed Coordination Decision Making

Designing of large-scale cooperative multi-robot systems in nearly future is an intensively studying area in current multi-agent system research.It includes many appealing applications such as coordinating a group of UAVs or deploying multi-robot systems for urban search and rescue.In these system designs,a key challenge lies on building coordination algorithms matched the domains.They must be not only based on the physical multi-robot ad-hoc network that is open and dynamic,but also able to solve the coordination problem decentralized for different levels of decision tasks.However,existed literatures have shown that their general theoretical model of decentralized multi-agent based joint decision approach,even being applied for a partial coordination problem,has been proven as NEXP-COMPLETE.In the dissertation,our research is devoted to utilize the complex network attributes that have been proven to be feasible and effective in coordinating human society so as to solve the decentralized coordination problem in large-scale multi-robot systems by constructing heuristic algorithms at different layers of cooperation.Our research will be carried out as follows:(1)Since human society can be abstracted as a similar but more complex coordination system than a multi-robot system,we analyze the complex network attributes existed in human society and summarizes their potential impacts that may impact the large-scale multi-robot coordination so that our heuristic algorithms can be put forward.Those attributes include such as degree distribution,network radius,clustering coefficients.(2)We analyzed the requirement of building a large-scale multi-robot coordination system.We found that any regular system should include at least three cooperation levels.From up to down,they can be described as service scheduling level-information sharing level-physical data distribution level.Based on the definition of three levels,we build heuristic coordination algorithms by utilizing complex network attributes for all the three layers so that an integrated approach toward multi-robot coordination problem can be reached.(3)In data distribution layer,we build the heuristic algorithms inspired by complex network attributes analysis based on robots' physical ad-hoc network.The data distribution algorithm is built without the assumption of understand the context.It only needs its local data paths to build the partial observation of the complex network attributes in the physical network as well as the heuristic decision algorithm whether the data should be broadcast so as to well balance improving the data coverage to the team and minimizing redundant data transportation.The ad-hoc network adjustment algorithm helps robots make decentralized moving decision in an open and complex environment by making a good use of flat degree distribution effects that could well balance the robots'moving cost,surveillance coverage and future communication cost.(4)In the information sharing layer,we abstract a logical network.Based on the network,information sharing is to push information that critical to the coordination decision for each distributed robot in the constraint of partial observable to the environment.The objective of sharing such information must be relevant to some intrinsic attributes in multi-robot coordination,such as capabilities or ordinates in cooperation.By analyzing statistical data of information sharing behaviors and modelling with their complex network attributes,we build the information sharing network reorganization algorithms with either full or partial acknowledgement of the network in order to optimizing the information sharing performance.(5)In the service scheduling layer,we model the multi-robot task allocation as a service scheduling problem so as to design the service scheduling network model under robots5 service constraints and define their scheduling objectives.The complex network attributes in the dynamic service-scheduling network are analyzed,and their effects to the network are discovered.According to making use of those network attributes such as node degree,clustering coefficient and mediation,a heuristic service scheduling optimization algorithm is proposed so that efficient services between robots can be reached and the performance of carrying out complex tasks can be improved.As the last part,in the dissertation,we build typical simulation platforms according to different coordination layers of the multi-robot coordination.By comparing with related algorithms and analyzing their performance,it is manifested that by introducing complex network attributes and building distributed robots' local recognition algorithm to understand those attributes in the system,our approach can significantly improve the coordination performance of decentralized multi-robot systems.