of 7

RoboCupRescue 2014 Rescue Simulation League. Team Description. <SEU_Jolly(P.R.China)>

2 views7 pages


All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
RoboCupRescue 2014 Rescue Simulation League Team Description <SEU_Jolly(P.R.China)> Wei Niu, Shuang Cai, Jie Wu School of Mechanical Engineering, Southeast University Abstract: In
RoboCupRescue 2014 Rescue Simulation League Team Description SEU_Jolly(P.R.China) Wei Niu, Shuang Cai, Jie Wu School of Mechanical Engineering, Southeast University Abstract: In this paper, a task-state based decision making method will be introduced. Then we build an effective communication system structure. Besides, researches on the multi-agent coordination has also been made, which is based on clustering analysis and Q learning algorithm. 1. Introduction RoboCup Rescue Simulation System (RCRSS) is a large-scale Multi-Agent System (MAS) of urban disasters. In such a dynamic, partially observable environment, the action decision making is always the primary problems which needs to be effectively solved. Our code structure is shown in the graph below. Figure 1. Code Structure of SEU_Jolly The effectiveness of decision making needs a complete and accurate world modeling. So, we established different channel based communication models in diversified disasters for information sharing: the typical communication model and communication model under no center conditions. The latter model has some profitable characteristics such as adaptability, minimum time delay and virtually equally distributed channels. These characteristics especially enable us to build a more realistic world model under certain sharp conditions. As for decision making, we use task-state based decision method. A simplified decision process is shown in Fig.2. Basic low level action of moving is addressed to fulfill different needs of our agents in such a dynamic and uncertain system. Figure 2 Module Structure of SEU_Jolly Our main code structure is as Fig.3. There are 12 modules in our code. The most important modules include communication module, world model update module, path plan module and top agent module. They are the basic modules to construct all the code. The knowledge base of task-state decision module is updated by the world model update module. The communication module help s to update the world and execute the agents command. Path plan module is a basic module that every kind agent must use it to get a path to the destination. The BFS method is low efficiency, so we do some efforts to improve it. We use traditional a star method to explore the path. The top agent model is the agent task manage center. The 3 kind agents common task is done in this module and the world model update module is also called in this module. Figure 3. Basic Decision Process of Agents 2. Task-State Decision System [2] We adopt a task state system to help us to do the decision of agents activities. A task include task object and task flag. Task object is what to do the task. Task state is a kind of flag that indicate what kind of activity the agent wants to do. Task flag indicates the task s attribute. Task Object Agents Agent State Task Flag Ongoing Done Repeatable Figure 4. The Structure of a task The task flow of task-state system is showed as fig.5 below. Create information from environment Create information from communication Create Task & Select Task Send information Task Execution Send Action Figure 5. The agent task flow 3. Communication Communication module is a very important module to support world model update and the agent action execution. In the latest server, the RCRSS use variable channel count to replace fixed channel count. If the communication mode is fixed channel count, the distribution mode is based on the number of specific center. Now the channel count is variable, center is as an ordinary agent. We can give a definition of the communication problem. To connect agents by P2P channel, to achieve message sharing and task allocation, minimize message quantity and maximize information sharing rate. The constraint condition include agent number, center number, channel count, available channel count, message size, utter number, false rate and dropout rate. This is presented in our 2012 TDP[2]. domain. We have put large effort to promote our communication system. There are three issues in this Firstly, we design some coding algorithms to overcome the channel noise, aiming to get a relatively low error probability. Secondly, our communication system is able to evaluate the channels and distribute different kind of messages among these channels in a proper way so that we can get a relatively high efficiency. Thirdly, we develop a communication system which can adapt to different communication environments, form good condition with large bandwidth and low bit error rate to poor condition with small bandwidth and high bit error rate. Here is the hierarchy of our communication system. Communication System Voice Module Coding Module Radio Module Spreading Module Distribution Module Evaluation Module Module Figure 6. Communication System Structure (1) Coding Module Coding module is a general module which is used in both voice and radio communication. To get a balance between efficiency and reliability, we use different coding algorithms. Coding Algorithm LEMPEL-ZIV coding Parity-check coding Hamming coding Features Source-coding algorithm for message compaction Available in Radio Module YES Available in Voice Module Simple error-control coding algorithm YES YES Error-control coding with a large redundance and the ability to correct bit error YES NO NO (2) Evaluation Module The fundamental module is to evaluate the channels so that we can rank them and make a good distribution. Since there are two parameters, bandwidth and bit error probability, with each channel, we take a practical method to realize the evaluation. We design a protocol which is only used at the beginning of the simulation. Each channel is allocated to two agents called e-sender and e-receiver. The e-sender is responsible to send a large number of channel-testing messages to the e-receiver and the latter evaluates the channel according to how many messages it receives. (3) Distribution module Distribution module is also available in both voice and radio channel, however, with several differences. Radio channel distribution is relative more complex. Given a set of channel resources and communication requirements, the function of the module is to distribute different kind of messages among these channels in a proper way. The algorithm is to rank the channels according to the result of evaluation module. The communication requirements of messages are also sorted. We use greedy strategy to satisfy the requirements. (4) Spreading Module This module is the essential part of the voice communication, especially useful when the condition is so poor that radio is nearly not available. The spreading pattern of messages through voice channel is quite different because of limited transmission distance. It s completely dynamic, distributed and local. We take advantage of communication network to model this spreading pattern. Each agent is a node of the network. The agent which is willing to send the message is active while others are inactive. The active node will continue to broadcast the message for several cycles and turn those adjacent nodes into active state. With this model,we do so analysis and simulation and it shows that on average each voice message should repeat more than 30 cycles before it is wildly spreading. 4. Multi-agent Coordination Focusing on rescue tasks, we try to realize multi-agent coordination in the following two steps, as is shown in Figure 7: dispersed tasks are combined into task package through clustering analysis as is shown in the big circle; then take task package as the input of coordination and make space for action and state with the assistance of Q learning algorithm. In Figure 7,the black dots are the known location of civilians, triangle represents the state and line is the action. Different actions can be chosen at different states, while the chosen action leading to another state. Our terminal goal is to reach a state that the task package is fully completed Figure 7. Steps to realize multi-agent coordination 4.1 Clustering analysis The method this paper puts up with is based on improved artificial immune algorithm, and can be realized through the following steps, as shown in Fig 8. Take location of civilians as antigens, and with the help of the algorithm, we can combine related civilians into cluster or say task package, and antibody is the centre of the cluster. Begin Antigen recognition Antibody initialization N Adding memory cells Calculated affinities Solved Select individuals Y Clone best individuals Variation End Group of antibodies Fig 8. The flowchart of algorithm Memory cells can help to store excellent solutions, which can be used as initial antibodies in the next round of clustering to make the whole process dynamical and at the same time speed up calculation. 4.2 Q learning In Q learning, the function Q(s, a) to evaluate learning actions is defined as the biggest conversion of the cumulative returns starting from the state s and using action a as the first action, that is, the immediate return of performing action a at state s, plus the rewards for the following strategies.. (1) (1) action space (i) Common actions of all agents: Move, Search, Rest. (ii) Actions of AT: Rescue: SaveAgent, SaveCivilian, SaveMyself; Load; Unload. (iii) Actions of PF: Clear: ClearBlockedRoadToRefuge, ClearNearBlockade, ClearEntrance, ClearMainRoad; Exploration. (iv) Actions of FB: WaterFill; Extinguish: ExtinguishDangerousBuilding,ExtinguishNearFire, ExtinguishFromRefuge. (2) state space in RCRSS (i) Common states of all agents: MovingToRefuge, MovingToPartition, RandomMove, Exploring. (ii) States of AT: MovingToHuman, RescuingHuman, LoadingHuman, TakingCivilianToRefuge, UnloadingHuman, SavingMyself. (iii) States of PF: GoingToBlockedRoad, ClearingBlock, ClearingPath, ClearingRefugeEntrance, ClearingMainRoad. (iv) States of FB: MovingToFireArea, Extinguishing, FillingWater, GoingToRefugeToRefillWater, GoingToHydrantToRefillWater. (3) value functions Use three functions of fieriness, buriedness and blockness respectively to evaluate the work of FB, AT and PF. If the values of the functions shrink after the agent took an action, then reward the agent. Besides, the fulfillment of rescuing the wounded, putting out fire and other important tasks will get the bonus. 5. Conclusion In this paper, we presented a brief overview of the structures and approaches designed and implemented in SEU_Jolly after RoboCup First of all, we want to build a complete and accurate world model via communications among different agents. Second, we adopt a new task-state decision system to improve our agents decision. Then, various techniques have been tried or implemented in our code to deal with noisy, varied, real-time and dynamic disaster environments. Finally, we tried a new method to realize multi-agent coordination. For the future, we plan to thoroughly test our code, modify minor bugs and use other Artificial Intelligence methods in order to establish an effectively cooperative team of agents in such a complex multi-agent domain to diminish the side effects of urban disasters. 6. Reference 1. RoboCup-Rescue Simulation Manual, RoboCup Rescue Technical Committee (2000). 2. Huang Zhourong, Guan Daqi, Shi Fabin. SEU_Jolly 2012 Team Description. 3. Guan Daqi, Ouyang Jin, Wang Huijun. SEU_RedSun 2011 Team Description. 4. Guan Daqi, Chen Ning, Jiang Yinhao. SEU_RedSun 2010 Team Description. 5. Meng Qingfa, Guan Daqi. SEU_RedSun 2009 Team Description. 6. Guan Daqi, Xu Yingqiu, Tan Yingzi. Particle Filter Based Study of Fire Forecasting in RCRSS. 7. Jiang Yinhao, Xu Yingqiu, Tan Yingzi. MST & SP Based Traffic Clearing and City Search in RCRSS.
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks