Cooperative Hunting by Multiple Mobile
Robots Based on Local Interaction
Zhi-Qiang Cao, Min Tan, Saeid Nahavandi & Nong Gu
1. Introduction
Open Access Database www.i-techonline.comThe problem of multi-robot coordination and cooperation has drawn great interest in recent years [1]. Generally speaking, for a given task, utilizing more than one robot may enhance the quality of the solution. Furthermore, many inherently distributed tasks must require a distributed solution. However, if the robots are not properly organized, the interference among them will block the task. Many challenging issues should be considered carefully. In this paper, we conduct our research in the context of multi-robot hunting.
The hunting task concerning mobile robots and its target to be hunted is a particular challenge due to the nature of unknown and irregular motion of the target. In order to coordinate the motion of multiple mobile robots to capture or enclose a target, a novel feedback-control law [2], linear autonomous system [3] and Multiple Objective Behavior Coordination [4] have been used. Other related works including pursuit game [5]- [7], whose environments are usually modeled in grid. In this chapter, we choose non-grid environments where each robot with a limited visual field moves in any collision-free direction.
This chapter considers a typical hunting task where multiple mobile robots (pursuers) cooperatively hunt an invader with certain intelligence in unknown environments. After the invader is found, its position information is broadcasted. If each robot knows where other robots are, it may take action from the group’s perspective. However, this will generate a communication burden that is too heavy to be practical. An approach where no positions of the robots are exchanged must be pursued. With less information, what action should the individual robot take? In this paper, an approach called Cooperative Local Interaction (CLI) is proposed to achieve cooperative hunting.
This chapter is organized as follows. Section 2 describes CLI approach where the hunting task is divided into four states and the detailed design in each state is given. In section III, the motion strategies for the invader are designed. Simulations are conducted in section IV and section V concludes the chapter.
2. CLI Approach
Assume that a multi-robot team is used to perform a hunting task. We label each robot Ri(i=1,2,...,N)∈ℵ. In order to avoid possible collisions, a range sensor model Srange is used to perceive the environment. We assume that the robots and the invader can see each other
Source: Cutting Edge Robotics, ISBN 3-86611-038-3, pp. 784, ARS/plV, Germany, July 2005 Edited by: Kordic, V.; Lazinica, A. & Merdan, M.
397
with the same range as that of Srange. Each robot may recognize other teammates and also can recognize the invader.
The task is divided into four states, which are as follows:
search state ⎯ each robot will search the environment until the invader is found.
pursue state ⎯ when a robot knows the position of the invader either by perception or by
communication and it thinks that the occasion to catch the invader hasn’t come yet, it keeps pursuing the invader.
catch state ⎯ when a robot thinks that the condition to catch the invader has been met, it
will catch the invader within a period of time.
predict state ⎯ after a robot loses track of the invader, it will predict the invader within a
period of time.
The central idea of CLI approach can be stated as follows: each robot determines its current state, makes decisions based on the information of the invader and other robots near it. The task is executed through local interaction among the robots. In the following, the detailed design in each state is introduced.
2.1 Search State
The robot endeavours to find the invader in the search state. The individual robot keeps away from other robots to utilize the resources better when it sees them (Boolean variable b1=1), and in other cases (b1=0) it moves randomly. Regardless of initial distribution of robots and the environment’s shape, an effective search can be accomplished. The robot’s moving direction (xr,yr)T is as follows.
⎧⎡pcx−pnex⎤22⎪⎢⎥/(pcx−pnex)+pcy−pney
⎡xr⎤⎪⎢⎣pcy−pney⎥⎦=⎨⎢⎥y−⋅cos(τρ)−sin(−τ⋅sigρ)⎤⎡xd⎤sig⎣r⎦⎪⎡
⎥⋅⎢⎥⎪⎢−⋅−⋅sincosτρτρ()()sigsig⎣⎦⎣yd⎦⎩
()b1=1b1=0
(1)
where (pcx,pcy)T, (pnex,pney)T are coordinates of the robot and another one nearest to it, respectively; (xd,yd)T refers to the robot’s heading; τ is an angle randomly rotated; ρ(ρ∈[0,1]) is a random number and sigρ=⎨
2.2 Pursue State
⎧−10.5>ρ≥0
.
⎩11≥ρ≥0.5
Let
PT
,
CT
denote the current position of the invader and its center, respectively.
position P(P∈℘(χ1,χ2]) to the invader is within (χ1,χ2]. For robot Rq∈ℵ, when its position Pr(q)∈℘(χ1,χ2], the robot is called a (χ1,χ2] robot.
Once a robot acquires the information of the invader, according to the distance to the invader, three zones can be generated and they are ℘(0,xnear], ℘(xnear,xfar] and ℘(χfar,+∞), where χnear and χfar(xfar>xnear) both are parameters determined by the robot’s maximum sensing range and its radius. Only when a robot is a (0,xnear] robot is it meaningful to judge whether the condition to catch the invader is satisfied. 398
⎫⎧
℘(χ1,χ2]=⎨Pχ1 Step_1: if Ni≥3, the robot chooses a mnb. Step_2: when Ni is an even number, the robot obtains Pri(minmnb), which is Pri(m) that makes the angle between coordinate system iPTpr(mnb) and PTPri(m)(m=1,2,...,Ni,m≠mnb) minimal and establishes a pole i PTpr(mnb)+PTPriminmnb mnb Σeveni whose pole, polar axis direction are CT and ()2 , mnb respectively. If Ni is an odd number, the robot establishes a polar coordinate system Σoddi whose pole is CT with the polar axis direction of PTPri(mnb). mnbmnb Step_3: calculate the coordinates Psmnbi(λs,γs)(s=1,2,..,Ni) in Σeveni (or Σoddi) for all robots in ℵi, where γs∈[0,2π). π⎞⎡3π⎞ Step_4: When ∃mnb such that ∃γk∈⎡⎢,π⎟I∃γj∈⎢π,⎟(k,j=1,2,...,Ni), the condition to catch the invader is considered to be satisfied. When a robot thinks that the condition to catch the invader is not satisfied, it is in the pursue state and has to pursue the invader first. Considering any robot Ri, the local decision-making process is as follows. i (mn)(mn=1,2,...Nn), where Nn may Step_1: acquire the positions of all other robots near Ri Prn be null and it means there is not a robot near Ri (go to Step_6). If Nn>0, it establishes a polar coordinate system ∑ri whose pole, polar axis direction are CT and PTPr(i), respectively. Step_2: calculate the coordinates Plneari(µl,ϕl)(l=1,...,Nn) for all neighboring robots in ∑ri, where ϕl∈(−π,π]. Step_3: get the angle ϕmin that is the minimum of ϕl and the corresponding robot’s i (min). position Prn Step_4: if ϕmin is less than ς, Ri should endeavour to reduce or eliminate the interference with other robots (go to Step_5), otherwise, there is no need to consider other robots (go to Step_6), where ς=2π(Nn≤2) or ς= 3 ⎣2 ⎠⎣ 2⎠ 2π(Nn>2). Nn+1 i (ϖi,φi) for Ri in a polar coordinate system ∑imin whose Step_5: acquire the coordinate Pmin i (min), respectively. Naturally, we have φi=ϕmin. pole and polar axis direction are CT and PTPrn If φi>0, the coordinate of the robot’s ideal position in ∑imin should be Pdi(rdis,ς), otherwise, it should be Pdi(rdis,−ς), where rdis is χfar (when Ri is a (χfar,+∞) robot) or χnear−2∆ (in other cases). ∆ is a margin. Step_6: the ideal motion position Prd(i) for Ri should locate in PTPr(i) and PTPrd(i)=rdis. 2.3 Catch State For the robot Ri, once the condition to catch the invader is satisfied, it is in the catch state and will catch the invader by moving to the ideal position Prcd(i), which locate in PTPr(i) and PTPrcd(i)=rc(rc<χnear−2∆), where rc is so small that the invader cannot move any more when 399 most of the robots involved arrive at their ideal positions. The decision-making process is adopted within certain steps stepcatchwithout considering the condition to catch the invader. If the step number the robot moves reaches stepcatch, it means that the invader maybe breaks away from being caught. In this case, the relevant robots need to re-analyze the situation. 2.4 Predict State Because of the complexity of the task and its environment, the robots possibly lose track of the invader. For Ri, when it loses track of the invader, it is in the predict state and has to T predict the invader within certain steps steppredict based on previous invader position Ppre i and its motion information to find the invader again. We denote with Ppre the previous iTposition of Ri. If the invader escapes along PprePpre and moves in the maximum step size of T Ri, the suppositional escaping position of the invader Psup can be calculated. Thus the robot Thopes to move along Pr(i)Psup. If the step number Ri in the predict state moves reaches steppredict, it shows that it is difficult to find the invader by prediction. This requires Ri to re-search the environment. 2.5 Motion Strategy The above decision-making of each state generates an output (a moving direction or a motion position) without considering the obstacles. Therefore, an effective motion strategy is indispensable to make each robot move effectively and safely. It combines the corresponding output with readings from sensors to control the robot. The strategy proposed here may enable each robot to obtain its safe moving direction that has the least angle with its ideal direction on the premise of predetermined step size. 453627801Figure 1. The layout of sensors The robot adopts a range sensor model Srange to perceive the environment. The detecting zone of each sensor is a sector. Fig. 1 shows the layout of sensors whose numbers are assigned from 0 to 8 as starting from the reverse direction of the robot’s heading, which is shown in arrow. The robot can know the presence or absence of other objects in each sector as well as the distance to them. For any robot Ri, it establishes a polar coordinate system ΣRi whose pole and polar axis direction are its center and current moving direction, respectively. Denote Prr(ρr,θr) as the coordinates of the ideal motion position of Ri in ΣRi. 400 The coordinates of the detecting border of sensors St(t=0,1,...,8) in ΣRi are Pst(ρt,θt), where ρt is the maximum sensing range when no obstacle is detected, otherwise, reading from St after the invader is considered, and θt∈⎢−π+ coordinates of next position of Ri in ΣRi, where ρa is the step size determined by the robot’s current position, ideal position and maximum step size; θ is the angle it rotated. The goal is to seek θ within [−ζrmax,ζrmax] of current moving direction on the premise of predetermined ρa such that the robot moves along the collision-free direction that has the least angle with the ideal direction. Base on sensory information, the distances PaPst(t=0,1,...,8) from Pa to the detecting border of each sensor should be greater than or equal to a safety distance Dsafe determined by the robot’s velocity and its radius, namely, PaPst≥Dsafe(t=0,1,...,8) (2) The final value of θ should satisfy eq. (2) and make θ−θr a minimum. Considering the tth sensor, we have (ρacosθ(t)−ρtcosθt)2+(ρasinθ(t)−ρtsinθt)2≥Dsafe (3) where θ(t) are the values of θ satisfying the condition of the tth sensor in eq. (2). From eq. (3), it can be obtained that cos(θ(t)−θt)≤ ρa2+ρt2−Dsafe2 2ρaρt =D (4) ⎡⎣2π2π(t+1)⎤t,−π+⎥. 99⎦ We denote with Pa(ρa,θ) the When ρa−ρt≥Dsafe is satisfied, θ(t)∈[−ζrmax,ζrmax]. When ρa+ρt Any value within the range of θt should be suitable for the above equation, therefore, 72π2π⎡ ππarccos,arccosDtD−+−++ 999999⎦⎢⎣⎩⎣ when arccosD≤8π is satisfied, and θ(t)∈Φ, when arccosD>8π is satisfied. 99 252π2π⎤ ππarccos,arccos θ(t)∈⎨⎡DtDt⎥U−+−−+⎢ ⎧ ⎤⎫ t⎥⎬I[−ζrmax,ζrmax] (6) ⎦⎭ The set of the values of θ satisfying the conditions of all sensors is defined as Ω, which is the intersection of θ(t)(t=0,1,...,8). When Ω is not empty, the most preferred value of θ can be obtained to make θ−θr a minimum, or else, the proper θ cannot be found. In this case, the robot will turn right angle ζrmax without any change in its position. 3. Strategies for the Invader Assume that the invader adopts the same model as that of the individual robot. While the invader does not see any robot or static obstacle, it moves randomly; otherwise, it will 401 move along a safety direction determined by the safety-motion strategy. The invader establishes a polar coordinate system Σe whose pole is its center and the polar axis direction is its heading. Denote Pei(ρi,θi) as the coordinates of the detecting border of sensors Sei(i=0,1,...,8) in Σe, where ρi is the reading from Sei when it senses any object, or else, the sensor is ignored and for convenience ρi is far greater than the maximum sensing 2π2πQ(i+1)⎤i,−π+range of the invader; θi∈⎡⎢−π+⎥. Based on the invader’s current direction, (a multiple of 4) directions are generated and their set ℑ is depicted as follows. 2qπ(q=0,1,...,Q−1)⎪ ℑ=⎪⎬ (7) ⎨ζqζq=−π+ ⎧⎪⎩ ⎫⎪⎭ Q ⎣ 99 ⎦ The invader may move to the position Pnq(Ve,ζq) on the premise of the predetermined step size Ve without any collisions when the distance from the position to the detecting border of each sensor should be greater than or equal to a safety distance Lsafe influenced by the invader’s velocity and its radius, that is, di(ζq)=min(PnqPei)≥Lsafe(i=0,1,...,8) (8) When ∃ζq∈ℑ satisfying eq. (8), the invader is still capable of moving, otherwise, no feasible moving direction is available and the invader is captured. We label Ψ ππ⎞ as the set of all directions within ⎡−,⎟ of the current direction and ⎢ ⎣22⎠ strategy is used to select the best one ζ from all ζq satisfying eq. (8) in the set Ψ, and the best value should make dis(ζq) maximum, thus, dis(ζ)=maxdis(ζq)=maxmin(d0(ζq),d1(ζq),...,d8(ζq)) (9) ζq ζq ⎧2qπ⎛QQ3Q⎞⎫⎪⎪Ψ=⎨ζqζq=−π+−1⎟⎬. When the invader can still move, the safety-motion ⎜q=,+1,..., Q⎝444⎪⎠⎪⎩⎭ If ζ is found, the invader will rotate ζ with the step size Ve, or else, it only turns right π. 2 4. Simulations In the following simulations, a random noise Dd with a mean µ and a variance σ2 is introduced into the individual robot’s sensing system in the form of Dm=Da(1+0.1⋅Dd), where Dm and Da are the simulated measured value and accurate value, respectively. In addition, considering the communication transfer among the robots may be failed occasionally, we assume that the robot cannot acquire the necessary information by communication with a probability of probc. A team of robots of ID 1,2, … is required to hunt a tricky invader T. The invader is regarded as one special case of a round robot. They have the same parameters: the radius, maximum step size and maximum sensing range are 0.2, 0.1 and 3.0, respectively. µ, σ2 in the random noise are 0 and 0.33, respectively. probc is 0.02. The parameters in CLI approach and safety-motion strategy are shown in Table I. 402 Parameter Value Parameter Value τ π18 χnearχfar rc steppredict 1.7 0.5 15 π2 1.3∆ stepcatch Dsafe Lsafe 0.15 15 0.3 0.39 ζrmax Q 72 —— Table 1. The values of parameters concerned (a) Before the invader is found (b) After the robotic system detects the invader Figure 2. The trajectories of the robots and the invader in simulation 1 Fig. 2(a)~(b) show the trajectories of the robots and the invader before/after the invader is found in simulation 1, respectively. Three robots are chosen to execute the task. From Fig. 2, it is seen that at the initial stage of motion, the robot of ID 1 and 2 will keep away from each other to enlarge their visual fields. When the robot of ID 2 detects the invader T, it informs other robots and the pursuit begins. Each robot decides its own movement. By local interaction among the robots, finally the invader is captured. (a) The initial environment (b) The coordinates of robots and the invader Figure 3. The simulation 2 In simulation 2, four robots are adopted and the environment is depicted in Fig. 3(a). Fig. 3(b) shows the coordinates of robots and the invader. We cans see that when the robot of 403 ID 1 is trying to move closer to the invader, the other three robots have already captured it. Although perhaps there are many robots (4 in this simulation) executing the task, it may be completed by local interaction among three robots. In general, more robots’ participation within certain range may shorten the task time. (a) The simulation environment (b) The variations of the robots’ states Figure 4. The simulation 3 Simulation 3 considers the case where a robot is suddenly abnormal. The initial environment is shown in Fig. 4(a). We denote with m_State the robot’s state. When m_State is chosen 1, 2, 3, 4, the robot is in the search, pursue, catch, and predict states, respectively. The variations of m_State for each robot as the task progresses are plotted in Fig. 4(b). The process may be described as follows: The robot of ID 2 sees the invader after a short period of searching, and it broadcasts the invader’s information to others. The other robots begin to move intentionally. However, several steps later, the robot of ID 2 suddenly becomes dysfunctional. The only source to provide the invader’s information is cut off. Thereupon other robots try to predict the invader, and it does not work. They have to re-search the environment. Later, the robotic system finds the invader again and ultimately captures it. To further confirm the validity of CLI approach, it is also compared with individual action (IA), an approach where each robot takes individual action regardless of other robots. Not 404 any local interaction among the robots adopting IA approach exists. A series of simulations (simulation 4) are conducted with the distance d increasing (see Fig. 5). For each d, 20 runs were performed and the results are shown in Fig. 6, which describes the relationship of average step numbers of the robots adopting different approaches versus d. It can be seen that although the robots adopting IA approach sometimes may shorten the completion time than those adopting CLI approach, in many cases, the selfish behaviour of the robots adopting IA approach will lead to a delay of completion time. From all simulations conducted, CLI approach is considered an effective one. Figure 5. The test environment of simulation 4 Figure 6. The comparison of different approaches for simulation 4 405 5. Conclusions This chapter has mainly focused on the problem of cooperative hunting by multiple mobile robots in unknown environments. Because the positions of the robots are not exchanged among them in order to reduce the communication burden, it is hard for each robot to make a global decision. A better idea is to complete the task by local interaction among the robots. In this chapter, an effective approach called Cooperative Local Interaction (CLI) has been proposed. The approach is robust and independent of the environments. As the invader actively tries to escape by adopting the safety-motion strategy, the difficulty of hunting is increased. The validity of CLI approach is supported by simulations. 6. References [1] Y. U. Cao, A. S. Fukunaga, A. B. Kahng, “Cooperative mobile robotics: antecedents and directions,” Autonomous Robots, 1997, 4(1), pp.7-27 [2] H. Yamaguchi, “A cooperative hunting behavior by mobile-robot troops,” International Journal of Robotics Research, 1999, 18(8), pp.931-940 [3] H. Yamaguchi, T. Arai, “Distributed and autonomous control method for generating shape of multiple mobile robot group,” in Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS’94, Munich, Germany, 800-807 [4] Paolo Pirjanian, M. J. Mataric, “Multi-robot target acquisition using multiple objective behavior coordination,” in Proceedings of the 2000 IEEE International Conference on Robotics and Automation, San Francisco, CA, 2000: 2696-2702 [5] J. Denzinger, M. Fuchs, “Experiments in learning prototypical situations for variants of the pursuit game,” in Proceedings 2nd International Conference on Multi-agent Systems, 1996, pp.48-55 [6] Ono, N., Fukumoto, K. and Ikeda, O, “Collective Behavior by Modular Reinforcement-Learning Animats,” in Proceedings of the 4th International Conference on the Simulation of Adaptive Behavior, 1997: 618-624 [7] R. Vidal, S. Rashid, C. Sharp, O. Shakernia, J. Kim, S. Sastry, “Pursuit-evasion games with unmanned ground and aerial vehicles,” in Proceedings IEEE International Conference on Robotics and Automation, 2001, pp.2948-2955 406 This book is the result of inspirations and contributions from many researchers worldwide. It presents acollection of wide range research results of robotics scientific community. Various aspects of current researchin robotics area are explored and discussed. The book begins with researches in robot modelling & design, inSecond chapter deals with various sensor systems, but the major part of the chapter is devoted to roboticvision systems. Chapter III is devoted to robot navigation and presents different navigation architectures. Thewhich different approaches in kinematical, dynamical and other design issues of mobile robots are discussed.chapter IV is devoted to research on adaptive and learning systems in mobile robots area. The chapter Vspeaks about different application areas of multi-robot systems. Other emerging field is discussed in chapter VI- the human- robot interaction. Chapter VII gives a great tutorial on legged robot systems and one researchoverview on design of a humanoid robot.The different examples of service robots are showed in chapter VIII.Chapter IX is oriented to industrial robots, i.e. robot manipulators. Different mechatronic systems oriented onrobotics are explored in the last chapter of the book.How to referenceIn order to correctly reference this scholarly work, feel free to copy and paste the following:Zhi-Qiang Cao, Min Tan, Saeid Nahavandi and Nong Gu (2005). Cooperative Hunting by Multiple MobileRobots Based on Local Interaction, Cutting Edge Robotics, Vedran Kordic, Aleksandar Lazinica and MunirMerdan (Ed.), ISBN: 3-86611-038-3, InTech, Available from:http://www.intechopen.com/books/cutting_edge_robotics/cooperative_hunting_by_multiple_mobile_robots_based_on_local_interactionPhone: +86-21-62489820 Fax: +86-21-62489821 因篇幅问题不能全部显示，请点此查看更多更全内容