WO2012148013A1

WO2012148013A1 - Method of searching invader in roadmap based environment

Info

Publication number: WO2012148013A1
Application number: PCT/KR2011/003034
Authority: WO
Inventors: Tareq Rezaul HAQUE; Chang Hwan Kim
Original assignee: Korea Institute Of Science And Technology
Priority date: 2011-04-26
Filing date: 2011-04-26
Publication date: 2012-11-01

Abstract

A method of searching invader in roadmap based environment includes determining virtual boundary which is defined based on the average velocity of searching robot, estimated invader's velocity, initial position of invader and environment constraint; along with virtual boundary the number of searching robots and their job positions on the edges of the virtual boundary are determined; Path planning for the searching robots to reach their job positions; and to search the virtual boundary appropriate job node is selected according to cost function till searching of all the nodes inside virtual boundary is over.

Description

METHOD OF SEARCHING INVADER IN ROADMAP BASED ENVIRONMENT

The present invention relates to multi-robots systems; and, more particularly, to cooperative search and path planning by multi-robots.

Recently, researchers have shown much interest in multi-robot systems and have frequently employed multi-robot teams to complete tasks that cannot be accomplished by a single robot. In cases of search and coverage algorithms, researchers have preferred multiple robots because of their robustness and quick completion of tasks. Various solutions have, thus, been proposed considering different environments, vehicles and resources.

McGee and Hendrick derived optimal strategies to guarantee capture under certain conditions when the target velocity is assumed to be bounded and sensing occurs within a finite limit. But, the bounding strategy can only be ensured in circular obstacle-free environments (T. G. McGee and J. K. Hedrick, “Guaranteed strategies to search for mobile evaders in the plane,” in Proceedings of the American Control Conference, Minneapolis, MN, 2006, pp. 2819 - 2824.). LaValle and Guibas developed pursuit-evasion strategies for multiple pursuers in polygonal environments (L. Guibas, J. Latombe, S. LaValle, D. Lin, and R. Motwani, “Visibility based pursuit-evasion in a polygonal environment,” Intl Journal of Computational Geometry and Applications, 9(5):471494, 1999.). Their algorithm discretizes polygonal environments into conservative visibility regions and then uses an information space approach to develop complete algorithms that guarantee capture in simple environments. Gerkey et al. extended these methods to cases where the pursuer has a limited field-of-view (B. Gerkey, S. Thrun, and G. Gordon, “Visibility-based pursuit-evasion with limited field of view,” Intl Journal of Robotics Research, 25(4):299315, 2006.). For a single pursuer, these algorithms are guaranteed to find a solution if one exists. But in the presence of multiple pursuers, however, they lose this property. Additionally, these algorithms are difficult to extend to complex environments because of the total number of cells necessary in a conservative visibility discretization. These algorithms are also not applicable to complex environments in which capture cannot be guaranteed. Sarmiento et. al. present a framework for searching polygonal environments with multiple robotic pursuers using a one-step cost heuristic(Sarmiento, R. Murrieta-Cid, and S. Hutchinson, ”A Multi-robot Strategy for Rapidly Searching a Polygonal Environment,” in Proc. 9th Ibero-American Conf. on AI, Puebla, Mexico, 2004.). But they did not extend this work to mobile evaders, and they did not present results in large-scale environments.

T. Balch and R. Arkin presented the analysis of the effects of different kinds of communication on the performance of teams of mobile robots that performed tasks like searching for objects or covering a terrain (T. Balch and R. Arkin, “Communication in reactive multi-agent robotic systems,” J. Autonomous Robot., vol. 1, no. 1, pp. 2752, 1994.). A family of robust multi-robot ant-based algorithms, which used approximate cellular decomposition, was presented by I. Wagner et. al (Wagner, M. Lindenbaum, A. Bruckstein, “Mac vs. pc determinism and randomness as complementary approaches to robotic exploration of continuous unknown domains,” International Journal of Robotics Research 19 (1) (2000) 1231.). The algorithms are provably robust, but are not necessarily efficient: In contrast to the minimal capabilities of ant-robots (other than pheromone use), our algorithms make use of the robots' memory and communicate to carry out efficient path.

In any search and coverage problem, most of the solutions are solved by decomposing the area into grid cells. This way of solution is applicable for an open space such as a forest and for sweeping purposes. But to provide security to some secure area like a housing society, a park, or an industrial farm, it cannot be thought as composed of grids because the whole area may not be reachable or some physical constraints may be present. For example, robots are only allowed to move through specified roads or more importantly, most of the times it is very difficult for wheeled mobile robots to move around in uneven terrain which imposes constraints on their mobility, and hence, we need a different solution. For these kind of scenarios, we propose the newly developed Simultaneous Online Search Algorithm (SOSA).

The present invention provides a method which defines a Virtual Boundary to bound the invader and big enough to search by the searching robots.

Further the present invention provides Simultaneous Online Search Algorithm (SOSA).

Further the present invention provides the method of searching invader to reduce redundancy.

In accordance with the present invention, there is provided a method of searching invader in roadmap based environment includes determining virtual boundary which is defined based on the average velocity of searching robot, estimated invader's velocity, initial position of invader and environment constraint; along with virtual boundary the number of searching robots and their job positions on the edges of the virtual boundary are determined;

Path planning for the searching robots to reach their job positions; and to search the virtual boundary appropriate job node is selected according to cost function till searching of all the nodes inside virtual boundary is over.

In multi-robot system collision may occur. While using the present invention collision chance is less because searching robots always search for unsearched nodes or nodes those are not booked by other robots. This also minimizes the occurrence of overlap. And minimum occurrence of overlap will reduce the search time.

The present invention ensures maximum use of all searching robots because it is an online search path planner. Distance between job nodes usually varies. In case of offline implementation of SOSA, if planner plans one job node for each searching robot in each iteration then path length of each searching robot will be different from each other. As a result some searching robot will stop searching before completion of searching entire virtual boundary. In the present invention when a searching robot reaches its job node then plan its next job node. And it continues planning till all the job nodes inside virtual boundary are searched.

The present invention does not have any invader position to plan search path. The present invention always looks for unsearched or uncovered node. It looks for n next nodes in all reachable directions. After adding this cost with other costs the present invention determine next job node.

The present invention does not depend on the shape of the virtual boundary. Because while planning for search path the present invention only consider the nodes inside the virtual boundary. So it does not matter what is the shape of the virtual boundary.

The objects and features of the present invention will become apparent from the following description of preferred embodiments given in conjunction with the accompanying drawings, in which

Fig. 1 describes a diagram showing the environment representation denoting polygons (p), vertices (v), and nodes (n);

Fig. 2 describes a diagram showing a scenario when the searching invader is first detected;

Fig. 3 describes a diagram showing virtual boundary representation;

Fig. 4 describes a flowchart showing how to determine virtual boundary and the number of searching robots;

Fig. 5 describes a flowchart of simultaneous online search algorithm (SOSA);

Fig. 6 describes a flowchart showing how to find minimum cost job node

from a searching robot’s current node;

Fig.7 describes a diagram of reachable node representation that means from a node which other nodes searching robot can move;

Fig.8 describes a diagram of tree view of reachable and booking nodes according to Fig.7.

The present invention now will be described more fully hereinafter with reference to the accompanying figures, in which embodiments of the invention are shown. This invention may, however, be embodied in many alternate forms and should not be construed as limited to the embodiments set forth herein.

Accordingly, while the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit the invention to the particular forms disclosed, but on the contrary, the invention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the claims. Like numbers refer to like elements throughout the description of the figures.

The present invention is described below with reference to block diagrams and/or flowchart illustrations of methods and/or display driver chips according to embodiments of the invention. It is understood that some blocks of the block diagrams and/of flowchart illustrations, and combinations of blocks in the block diagrams and/or flowchart illustrations, may be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, and/or other programmable data processing apparatus, create means for implementing the functions/acts specified in the block diagrams and/or flowchart block or blocks.

These computer program instructions may also be stored in a computer readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instructions which implement the function/act specified in the block diagrams and/or flowchart block or blocks.

The computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer-implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions/acts specified in the block diagrams and/or flowchart block or blocks.

As will be appreciated by one of skill in the art, the present invention may be embodied as a method, data processing system and/or computer program product. Thus, the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects, which may be collectively referred to herein as a “circuit” or “module”.

It should also be noted that in some alternate implementations, the functions/acts noted in the blocks may occur out of the order noted in the flowcharts. For example, two blocks shown in succession may in fact be executed substantially concurrently or the blocks may sometimes be executed in the reverse order, depending upon the functionality/acts involved.

Environment representation

Environment is represented by Graph G and G = (V, P) Where V is a set of r vertices and all the vertices v_i (i = 1 ~ r) will contain coordinate information. Roads are represented by polygon P_i (i = 1 ~ k)} where k is the number of polygons to represent the roads within the environment and P_i = (v₁~ v_m). Here m is the number of vertices of i^th polygon. The polygon edges which are common to two polygons are portal edges and the midpoint of portal edge is denoted as a node. Nodes are actually used by a path planner. Another additional table is also generated while initialization i.e. reachability table. It contains the reference of all reachable nodes for each node.

Referring to Fig. 1, P is the set of polygons, V is the set of vertices (white circles) and n is the set of nodes (red circles). Edge (v₃, v₄) is the common edge of polygon P₁ and P₂. So midpoint of edge (v₃, v₄) is n1 which is a node. Again edge (v₃, v₆) is the common edge of polygon P₂ and P₆. So n₂ is a node. This way all the nodes are determined. After finding nodes next job is to find reachable nodes from a node. So from Fig. 1 we can see for node n₁'s reachable nodes are n₂ and n₃. Node n₂'s reachable nodes are n₁, n₃ and n₇. This is the way to determine the reachable node for each node.

Environment representation has big impact on our search method. So while designing new environment, we need to make sure there is enough node inside virtual boundary to cover entire area. Actually, a node's distance from its reachable node should not be more than the sensor coverage range.

Defining virtual boundary

Virtual boundary will confine the searching robot not to search the area with no chance of invader's presence. While determining virtual boundary, job positions and the number of searching robots are also determined. Job positions are appropriate positions on the edge of virtual boundary for searching robots to start searching. Referring to Fig.4, Iterative process is employed to determine the virtual boundary and number of searching robots.

Eq.(1)

Eq.(2)

Here, T_* is the time when searching robot meet the invader if they move towards each other. Referring to Fig.2, D is the straight distance between invader and the closest searching robot. Referring to Fig.3, R_I is the initial circular virtual boundary (ICVB) radius, V_R is the searching robot's average velocity and V_T is the invader's approximated velocity.

The time the farthest searching robot takes to reach the closest intersection point between road and virtual boundary at the same time the distance traveled by the invader is R_I. Equations Eq. (1, S403) and Eq. (2, S404) are used to find R_I. Referring to Fig.3, Eq. (1) is only used to calculate T_* at the first iteration of the algorithm.

Referring to Fig.6, final circular virtual boundary (FCVB) radius - If invader moves other than towards searching robot, then by the time searching robot reach virtual boundary, invader will be out of virtual boundary. So R_I needs to be increased to make sure invader is inside virtual boundary. To make sure boundness, distance travel by invader within the time searching robot takes to search virtual boundary need to add with R_I (S405).

Eq.(3)

Here, R_F is final circular virtual boundary radius. D_R is the straight distance from searching robot's job position to other end of virtual boundary. But for the first iteration while virtual boundary is not defined then D_R = 2R_I.

Referring to Fig.3 virtual boundary (VB) is to be determined. Because the searching robots are only able to move through the roads, so it's better to think virtual boundary as a rectangular area, whose length and width is equal to 2R_F. If circular virtual boundary is not fully inside the secure area then length and width of virtual boundary will be different. The number of searching robots (N_R) is determined based on the coverage of edge length. That means how many searching robots need to cover one edge of virtual boundary by its sensor.

Eq.(4)

After determining the number of searching robots (N_R), if NR is greater than the total available number searching robots (A_R) then R_F needs to be increased to make the boundary boundable for less number of searching robots to search.(S406, S407, S410, S411)

Eq.(5)

Next problem is to choose the job position for searching robots. Job positions are chosen from a set of candidate job positions (S408). Candidate job positions are the positions where roads are intersected by the edges of virtual boundary. To choose job positions, searching robots are assigned priority based on distance from invader's detection point. The farthest searching robot is assigned the most priority. After finding job position A^* path finder is used to find the shortest path for searching robot's current position to its job position. Fig. 4 describes the whole process of determining virtual boundary and the number of searching robots.

Eq.(6)

Eq.(7)

Here, P_L is the max path length among the paths from searching robot's current position to its job position and in Eq. (7), T_* is the time taken by searching robot to reach job position.

When all the selected searching robots satisfy Eq. (6), they can reach their job positions and search virtual boundary. If Eq. (6) is unsatisfied then Eq. (7) is used to set new time limit to define inner circular virtual boundary radius (R_I). And then based on new R_I and previous iteration virtual boundary information we will again define new virtual boundary and find job position (S412, S413).

In any case, if the number of searching robots becomes more than the total number of searching robots then the number of searching robots will be fixed to the total number of searching robots. And the algorithm will increase the size of virtual boundary to ensure boundless for the available searching robots. After using all the available searching robot, if Eq. (6) is not satisfied then entire area will be virtual boundary. After reaching job position, SOSA plans the path to search virtual boundary.

Simultaneous online search Algorithm (SOSA)

SOSA is a search path planner which ensures effective and minimum redundant search path in roadmap based environment. SOSA's job is to search all the nodes inside virtual boundary. While search planning a searching robot chooses its most feasible reachable node as job node and book n nodes as the future job node. The node which can be the job node after a searching robot reaches its current job node is a future job node. And when the next searching robot will look for its job node, it will consider other searching robots' job nodes and booking nodes.

Fig. 5 shows the flow chart of SOSA. In Fig.5, nRobot is the number of searching robot, i is the index of the searching robot and j is the index of reachable node from a searching robots current node. All the searching robots will move towards their job nodes, their first job is to search for invader. If invader is detected, search is completed. If invader is not detected, SOSA will check for each searching robot has reached its job nodes If not reached then searching robot index will increase and process will continue with next searching robot. And if a searching robot reaches its job node, SOSA will check if the search of entire virtual boundary has completed or not. If search completed without invader detection then it's an unsuccessful search. The term 'Search completed' means all the nodes inside virtual boundary should be searched. If search is not completed then final cost function will be called for all the reachable nodes of a searching robot's current job node and the minimum cost node will be chosen as next job node. This process will continue till all the nodes are searched.

SOSA's basic idea is to find out the minimum cost node of all reachable nodes from the current job node. From these reachable nodes, the node with minimum cost is considered as the next job node. Fig. 6 presents the whole process of finding the minimum cost job node. The final cost function to determine a reachable node's cost is described below

Eq.(8)

Eq.(9)

Eq.(10)

Eq.(11)

Here, T is the total cost of a reachable node to choose (S603). R_c is the cost for a searching robot to take turn to move to next reachable node and its maximum cost is π. L_c is an integer constant, a node returns L_c if it is booked by some searching robot. C_c is an integer constant, a node returns C_c if the node already considered as job node or it can be searched from a job node. A reachable node returns N_c if it is outside of virtual boundary and it's an integer constant. n is the number of job nodes to book by a searching robot and r is number of searching robots. From eqs. (9) ~ (11), we can see R_c returns the minimum value among cost terms and N_c returns the maximum value to influence the searching robots to search only inside virtual boundary. L_c and C_c are greater than R_c because searching robot should look for unsearched and not booked node. R_c is only useful when there is more than one node has same cost. C_c is greater than L_c because no need to search already searched node.

α is 1 if the reachable node is searched by the searching robot, 2 if the reachable node is the previous job node of the searching robot, 3 if the reachable node is the previous job node of the searching robot, 0 otherwise.

β is 1 if the reachable node within sensor range from the job node and if anyone of its reachable node is outside of the virtual boundary, 2 if the reachable node is outside, 0 otherwise.

According to Fig. 7 when a searching robot's job node is A and reachable node is D then β is 1 because one reachable node R of D is outside of virtual boundary. If D is a job node and it's reachable node R is out of virtual boundary so in this case β is 2. When A is a job node then it has three reachable nodes B, C and D. For these three reachable nodes, the final cost will be calculated and the minimum cost node will be chosen as the next job node.

Now, we discuss about fourth term (K_c) of the final cost function. K_c books n future job node and returns the cost to book n future job nodes. K_c's job is to go forward and collect the status of the nodes available in different direction (i.e. different reachable node). And calculate the cost for choosing a direction. All the cost will be added with final cost function (T). And reachable node with the minimum final cost is the next job node. Now we will see how K_c works. K_c uses B^* to book n future job node.

Eq.(12)

Eq.(13)

Here, B^* is the cost of a node to book while booking n future job nodes. γ returns the cost of choosing node which is already booked by itself. η is 1 when a chosen node is already booked itself else 0. And λ is 1 when it is within the sensor range from a node chosen by itself else 0. Three functions (C₁, C₂ and C₃) are used to compute the cost to book n nodes for a reachable node.

Eq.(14)

Here, C₁ is the cost to book searched node. b is the booking list and b_i is the i^th booking node for a reachable node.

Eq.(15)

Here, C₂ is the cost to book nodes which are already booked node by other searching robots and cost will more to book other searching robot's booking list's front node than rear node. If b_i is booked but not by the current searching robot then y_i is 1 else 0.

Eq.(16)

Here, C₃ is the cost to book nodes out of virtual boundary. If b_i is outside of virtual boundary then z_i is 1 otherwise 0.

So K_c= (C₁+ C₂+ C₃) is the cost from a reachable node to book n future job nodes. Here we want to give an example of term Kc according to Figs. 7 and 8. If a searching robot has reached its job node (A) then it will look for its next job node. For this example let n = 3. Node A has 3 reachable nodes (B, C and D). Now in B direction we will determine booking node using Eq. (12). For 1st booking reachable nodes of B are A, E, C and D. Among these four node E is the best choice because A is previous job node, D has a reachable node (R) outside VB and between E and C, to reach E searching robot does not require any angular velocity. For 2nd booking E's reachable nodes are B, I, H and G and here I will be the minimum cost reachable node from E. For 3rd booking, I's reachable nodes are H, J, E and G and here J is the best choice. So for node B chosen nodes to book are E, I, J. In the same way, for node C chosen nodes are Q, N, M. Now, using Eqs.(14) and (16) K_c will be calculated for booked nodes and will be added to final cost function of B, C and D. Among B, C and D which return the minimum will be considered as future job node. If C is the node with minimum cost node then BookingList (b) will be updated with the node Q, N, M for the current searching robot.

While the invention has been shown and described with respect to the preferred embodiments, it will be understood by those skilled in the art that changes and modification may be made without departing from the spirit and scope of the invention as defined in the following claims.

“Patrolling and Searching” by human are tedious, hard and sometimes hazardous. These problems can cause unsecure situations in secure area. So an alternative approach is to use technology to assist in these tasks through the use of multiple mobile robots to guard the grounds of secure area from intrusion and also search for intrusive presence if detected inside secure area.

But algorithm is necessary to control multiple mobile robots, so we developed Simultaneous Online Search Algorithm (SOSA) to control multiple mobile robots in searching and patrolling.

So, there is enormous applicability for our algorithm to be implemented in real environments like housing society, industrial area, museum, and government’s important places.

Claims

A method of searching invader in roadmap based environment includes

determining virtual boundary which is defined based on the average velocity of searching robot, estimated invader's velocity, initial position of invader and environment constraint; along with virtual boundary the number of searching robots and their job positions on the edges of the virtual boundary are determined;

Path planning for the searching robots to reach their job positions; and

Searching the virtual boundary appropriate job node is selected according to cost function till searching of all the nodes inside virtual boundary is over.
The method of claim 1, further comprising

determining the number of searching robots based on the virtual boundary.
The method of claim 1, wherein determining virtual boundary includes

Driving T_*, which satisfies the following relationship:

wherein T_* denotes the time when the searching robot meets the invader, D denotes straight distance between invader and the closest searching robot, V_T denotes the invader's approximated velocity and V_R denotes the searching robot's average velocity;

Driving R_I, which satisfies the following relationship:

Wherein R_I denotes the initial circular virtual boundary; and

Driving R_F, which satisfies the following relationship:

Wherein R_F denotes final circular virtual boundary radius, D_R denotes the straight distance from the searching robot's job position to other end of virtual boundary.
The method of claim 2, wherein determining the number of searching robots includes

driving N_R, which satisfies the following relationship:

Wherein N_R denotes the number of the searching robots, R_s denotes the radius of sensor in the searching robot.
The method of claim 4, after the driving New N_R, further comprising

Driving New R_F if N_R > A_R, which satisfies the following relationship:

New

Wherein A_R is the number of available searching robot.
The method of claim 5, after the driving New R_F, further comprising

Driving New T_* if P_L/V_R >T_*, which satisfies the following relationship:

New
The method of claim 1, searching the virtual boundary appropriate job node includes

driving the cost function T, which satisfies the following relationship:

wherein T denotes the total cost of a reachable node to choose, R_c denotes the cost for a searching robot to take turn to move to next reachable node and its maximum cost is π, C_c denotes an integer constant, a reachable node returns C_c if the node already considered as job node or it can be searched from a job node, a reachable node returns N_c if it is outside of the virtual boundary and it's an integer constant, K_c returns the cost to book n future job nodes,

whrerin α is 1 if the reachable node is searched by the searching robot, 2 if the reachable node is the previous job node of the searching robot, 3 if the reachable node is the previous job node of the searching robot, 0 otherwise,

wherein β is 1 if the reachable node within sensor range from the job node and if anyone of its reachable node is outside of the virtual boundary, 2 if the reachable node is outside, 0 otherwise.
The method of claim 7, wherein the driving the cost function T satisfies the following relationship:

Wherein L_c is an integer constant and the reachable node returns L_c if it is booked by some robot.
The method of claim 8, wherein the driving the cost function T satisfies the following relationship:
The method of claim 8, wherein the driving the cost function T satisfies the following relationship:
The method of claim 8, wherein the driving the cost function T further comprising Driving B^* for each booking position, which satisfies the following relationships:

;

Wherein γ returns the cost of the booking node which is already booked by itself, η is 1 when the booking node is already booked itself else 0, and λ is 1 when it is within the sensor range from the booking node chosen by itself else 0.
The method of claim 11, wherein driving K_c by using the minimum B^* of all the booking nodes, which satisfies the following relationship:

K_c= (C₁+ C₂+ C₃)

Wherein C₁ is the cost to book searched node, C₂ is the cost to book nodes which are already booked by other robots and cost will more to book other robot's booking list's front node than rear node, and C₃ is the cost to book nodes out of virtual boundary.
The method of claim 12, wherein driving K_c, which satisfies the following relationships:

Wherein b is the booking list and b_iis the ith booking node for the reachable node,

Wherein If b_i is booked but not by the searching robot then y_i is 1 else 0

Wherein b_i is outside of virtual boundary then z_iis 1 otherwise 0.