A hybrid EVSA approach in clustered search space with ad-hoc partitioning for multi-robot searching
- PDF / 6,138,603 Bytes
- 20 Pages / 595.276 x 790.866 pts Page_size
- 13 Downloads / 171 Views
RESEARCH PAPER
A hybrid EVSA approach in clustered search space with ad‑hoc partitioning for multi‑robot searching Upma Jain1 · Ritu Tiwari2 · W. Wilfred Godfrey1 Received: 24 December 2018 / Revised: 12 January 2020 / Accepted: 26 January 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract This paper examines the problem of multi-robot target searching in an unknown environment. Since no information is available about the targets, so the search is similar to the exploration problem. In this paper, a new method is proposed to improve the efficiency of exploration. The objective of the proposed approach is to minimize the exploration time by reducing the redundant coverage and computational overhead. For exploration, the concept of frontiers is being used. The following hypothesis formulated in order to improve the exploration: (1) Introduction of an ad-hoc partitioning method to handle redundant coverage. (2) Reduction of the search space by clustering (grouping) the frontier cells to minimize the computational overhead. (3) Introduction of methods for robots’ next position assignment problem, namely, nearest frontier-cluster center method when a single robot is searching in the sub-region. A hybrid of Egyptian vulture and simulated annealing based approach when more than one robots are searching within a sub-region. Performance of the proposed approach is evaluated through simulation in two different workspaces with a team size of 2 and 4 robots. Four different performance measures namely Redundant coverage, Object localization time, Exploration time and Exploration percentage are considered to evaluate the performance of the proposed method. Results show that proposed hybrid-EVSA method completes exploration much faster in both the workspaces with the team size of 2 and 4 robots as compared to other state of art approaches due to low computational overhead and reduced redundant coverage. Keywords Multi-robot system · Target searching · Exploration · Frontier-cluster · Ad-hoc partitioning
1 Introduction Searching for an object in an unknown environment can be formulated as an iterative procedure consisting of map updating, selection of a next goal and navigation to this goal and finishing when the object of interest is found [24]. Exploration represents the policy of the system to choose the next area to explore its environment. This system uses the information coming from its sensors or its neighbor robots [6]. * Upma Jain [email protected] Ritu Tiwari [email protected] W. Wilfred Godfrey [email protected] 1
ABV-IIITM Gwalior, Gwalior, India
IIIT Pune, Pune, India
2
For exploration various approaches have been proposed by researchers including leader-follower/line of sight [16, 35] exploration with environmental tagging [23, 45] graph theoretic or tree based approaches [4, 9, 18, 20, 28], nature or swarm inspired approaches [7, 25, 30, 32–34] and frontier-based methods [14, 15, 42]. In the leader-follower approaches, there is a leader robot which is followed by one
Data Loading...
