Research On Coalitional Games And Their Application In Disaster Emergence Response

Coalitional games have always been a very important and active topic in the field of multi-agent systems(MAS)and artificial intelligence.The reason is that a coalition provides a flexible way of collaborating,allowing some independent agents to form a collaborative team within a certain period of time,uniting to achieve complementary advantages and resource sharing,so that the goal can be achieved more intelligently,flexibly and efficiently.However,most of the existing research is limited to a certain environment,in which a quantitative description of the capabilities or resources possessed by each agent has to be given in advance.It is difficult for this certain description to adapt to the collaboration in an uncertain environment.Additionally,although coalitional game methods have been used in the fields of e-commerce,wireless networks,multi-robot collaboration,and so on,their applications need to be further expanded,especially in the field of disaster emergency response.Against the above background,this thesis first studies the problem of coalition structure generation in coalitional skill games(CSGs).Then,based on the idea of“disaster emergency response coalition",this thesis also explores the integration optimization problem of the allocation and scheduling of emergency relief supplies.Moreover,The integrated system of allocation and scheduling of emergency relief supplies for the Anhui provincial four-level reserve network is developed,which can provide a more scientific decision-making reference for the government to respond to major natural disasters efficiently and orderly.The main research contents and innovations of this thesis are as follows:(1)Coalitional Skill Games(CSGs)are a simple model of cooperation in an uncertain environment where each agent has a set of skills that are required to accomplish a variety of tasks and each task requires a set of skills to be completed,but each skill is very hard to be quantified and can only be qualitatively expressed.Thus far,many computational questions surrounding CSGs have been studied.However,to our best knowledge,the coalition structure generation problem(CSGP),as a central issue in CSGs,is extremely challenging and has not been well solved.To this end，two different computational intelligence approaches are herein evaluated:binary particle swarm optimization(BPSO)and binary differential evolution(BDE).In particular,we develop two stochastic search algorithms with two-dimensional binary encoding and corresponding heuristic for individual repairs.After that,we discuss some fundamental properties of the proposed heuristic.Finally,we compare the improved HBPSO and HBDE with the existing state-of-the-art algorithms for solving CSGP in CSGs.The experimental results show that our algorithms can find the same near optimal solutions with the existing approaches but spend an extremely short time,especially under the large problem size.(2)In the disaster emergency response,there is a natural intrinsic correlation between the allocation and scheduling of disaster relief supplies.It is obvious that the amount of relief supplies contributed by the reserve points and the location of the reserve points will inevitably affect the transportation time during the scheduling process and the response time of the entire emergency process.Therefore,it is more realistic to integrately optimize the allocation and scheduling of disaster relief supplies,which can improve the emergency response efficiency in general.To this end,this thesis introduces the"collaborative coalition" idea in coalitional games and tries to achieve the overall scheduling and cooperative engagement of multiple rescue units on the basis of the"disaster emergency response coalition(DERC)".Firstly,in terms of the agent coalition,the mathematical model of the emergency response network is constructed.Secondly,the Dijkstra algorithm and the emergency response time constraints are used to tailor the emergency response network,in which all the reserve points and dispatch points are reserved,and the new edges derived from the shortest,feasible paths between any reserve point and dispatch point are added.Thirdly,a two-dimensional integer vector encoding is designed to represent a solution of the integration optimization problem of the allocation and scheduling of multiple reserve points,multiple dispatch points,and various relief supplies.Additionally,the emergency response network is further tailored through extracting the heuristic information from the encoding.After that,a greedy algorithm on the basis of minimum travel time is developed to achieve the resource allocation of DERCs which have multiple members.Finally,the allocation and scheduling scheme is indicated on the emergency response network through decoding.Compared with the existing work,the experimental results show that the proposed fast hybrid search algorithm on the basis of heuristic and greedy strategies has an absolute advantage in terms of the total consumed time,which is less than 2%of the running time of the four comparison algorithms.Moreover,the proposed hybrid search algorithm also outperforms the four comparison algorithms on the overall performance in terms of the emergency response time and the transportation cost.(3)China is one of the countries in the world that are mostly affected by natural disasters.In China,natural disasters have many types,wide geographical distribution,high frequency of occurrence,and always result in heavy losses.However,compared with developed countries such as Europe,the United States,and Japan,China has a large gap in the scientific allocation and smart scheduling of relief supplies,and is still in a state of making decisions by leaders’ personal experience.The State Council clearly stated in the"Notice on the National Comprehensive Disaster Prevention and Mitigation Plan(2016-2020)" in.2016 that "the government needs to improve the standardization and modernization of disaster prevention and mitigation work,strengthen scientific and technological innovation,and effectively improve the scientific and technological support capabilities and levels for disaster prevention and mitigation." To this end,based on the Anhui Provincal four-level relief supplies reserve network,this thesis used Alibaba Cloud server architecture,Java Web back-end programming technology,MySQL,Baidu map API,front-end programming languages HTML,CSS,JavaScript and JQuery,etc.The thesis developed an integration system of allocation and scheduling of disaster relief supplies to effectively verify the uniformity and feasibility of various technologies,and provide a set of exemplary solutions for the government to respond to major natural disasters efficiently and orderly.