Conference Papers
Permanent URI for this collectionhttps://idr.nitk.ac.in/handle/123456789/28506
Browse
23 results
Search Results
Item Deploy and search strategy for multi-agent systems using Voronoi partitions(2007) Guruprasad, K.R.; Ghose, D.In this paper we analyze a deploy and search strategy for multi-agent systems. Mobile agents equipped with sensors carry out search operation in the search space. The lack of information about the search space is modeled as an uncertainty density distribution over the space, and is assumed to be known to the agents a priori. In each step, the agents deploy themselves in an optimal way so as to maximize per step reduction in the uncertainty density. We analyze the proposed strategy for convergence and spatial distributedness. The control law moving the agents has been analyzed for stability and convergence using LaSalle's invariance principle, and for spatial distributedness under a few realistic constraints on the control input such as constant speed, limit on maximum speed, and also sensor range limits. The simulation experiments show that the strategy successfully reduces the average uncertainty density below the required level. © 2007 IEEE.Item Multi-agent search using sensors with heterogeneous capabilities(International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS) info@ifaamas.org, 2008) Guruprasad, K.R.; Ghose, D.In this paper we introduce a new concept namely, generalized Voronoi partition and use it to formulate two heterogeneous multi-agent search strategies. The core idea is optimal deployment of agents having sensors with heterogeneous capabilities, in a search space so as to maximize search effectiveness. We address a few theoretical issues such as optimality of deployment, convergence and spatial distributedness of the control law and the search strategies. Copyright © 2008, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.Item Multi-agent search strategy based on centroidal Voronoi configuration(2010) Guruprasad, K.R.; Ghose, D.We propose a combined deploy and search strategy for multi-agent systems using Voronoi partition. Agents such as mobile robots (AGVs, UAVs, or USVs) search the space to acquire knowledge about the space. Lack of information about the search space is modeled as an uncertainty density distribution, which is known a priori to all the agents at the beginning of search. It is shown that when the agents are located at the centroid of Voronoi cells, computed with the perceived uncertainty density, reduction in uncertainty density is maximized. While moving toward this optimal configuration, the agents simultaneously perform search acquiring the information about the search space, thereby reducing the uncertainty density. The proposed search strategy is guaranteed to reduce the average uncertainty density to any arbitrary level. Simulation experiments are carried out to validate the proposed search strategy and compare its performance with sequential deploy and search strategy proposed in the literature. The simulation results indicate that the proposed strategy performs better than sequential deploy and search in terms of faster search, and smoother and shorter robot trajectories. ©2010 IEEE.Item Generalized Voronoi partition: A new tool for optimal placement of base stations(2011) Guruprasad, K.R.This paper presents a novel framework for placement of base stations (BS)s. A generalization of Voronoi partition is used, where, a set of node functions are used in place of the usual distance measure. Functions modeling the effectiveness of BSs at different locations in the region are used as node functions, and the locations of BSs as nodes or sites. Further the base stations are assumed to be heterogeneous and anisotropic. © 2011 IEEE.Item Egress: An online path planning algorithm for boundary exploration(Institute of Electrical and Electronics Engineers Inc., 2012) Guruprasad, K.R.; Dasgupta, P.We consider the problem of navigating a mobile robot that is located at any arbitrary point within a bounded environment, to a point on the environment's outer boundary and then, using the robot to explore the perimeter of the boundary. The environment can have obstacles in it and the location and size of these obstacles are not provided a priori to the robot. We present an online path planning algorithm to solve this problem that requires very simple behaviors and computation on the robot. We analytically prove that by using our algorithm, the robot is guaranteed to reach and explore the outer boundary of the environment within a finite time. © 2012 IEEE.Item Multi-robot terrain coverage and task allocation for autonomous detection of landmines(SPIE, 2012) Dasgupta, P.; Muñoz-Meléndez, A.; Guruprasad, K.R.Multi-robot systems comprising of heterogeneous autonomous vehicles on land, air, water are being increasingly used to assist or replace humans in different hazardous missions. Two crucial aspects in such multi-robot systems are to: a) explore an initially unknown region of interest to discover tasks, and, b) allocate and share the discovered tasks between the robots in a coordinated manner using a multi-robot task allocation (MRTA) algorithm. In this paper, we describe results from our research on multi-robot terrain coverage and MRTA algorithms within an autonomous landmine detection scenario, done as part of the COMRADES project. Each robot is equipped with a different type of landmine detection sensor and different sensors, even of the same type, can have different degrees of accuracy. The landmine detection-related operations performed by each robot are abstracted as tasks and multiple robots are required to complete a single task. First, we describe a distributed and robust terrain coverage algorithm that employs Voronoi partitions to divide the area of interest among the robots and then uses a single-robot coverage algorithm to explore each partition for potential landmines. Then, we describe MRTA algorithms that use the location information of discovered potential landmines and employ either a greedy strategy, or, an opportunistic strategy to allocate tasks among the robots while attempting to minimize the time (energy) expended by the robots to perform the tasks. We report experimental results of our algorithms using accurately-simulated Corobot robots within the Webots simulator performing a multi-robot, landmine detection operation. © 2012 SPIE.Item EgressBug: A real time path planning algorithm for a mobile robot in an unknown environment(2012) Guruprasad, K.R.This paper addresses the problem of path planning for a mobile robot in a region occupied by finite number obstacles. The region and the obstacles are not known a priori to the robot. We present an online path planning algorithm called EgressBug, that makes the robot reach any specified point in the space, and stops by reporting failure when the specified goal point does not belong to the free space. The proposed EgressBug algorithm uses simple move toward a point and wall following behaviors. The algorithm is illustrated with the help of examples, and paths generated by the EgressBug algorithm are compared with those generated by the Bug2 and TangentBug algorithms. © 2012 Springer-Verlag.Item A distributed algorithm for computation of exact Voronoi cell in a multi-robotic system(2012) Guruprasad, K.R.; Dasgupta, P.In this paper we propose an algorithm for distributed computation of Voronoi cell in a multi-robotic system. Each of the robots is assumed to know its own position and position of all other robots. The robots compute their Voronoi cells based only on this positional information, without any additional communication and cooperation with other robots. © 2012 IEEE.Item Distributed Voronoi partitioning for multi-robot systems with limited range sensors(2012) Guruprasad, K.R.; Dasgupta, P.We consider the problem of distributed partitioning of an environment by a set of robots so that each robot performs its operations in the region within the corresponding cell. Voronoi partitioning is one of the most attractive techniques that has been used to solve this problem. It has been used in several distributed multi-robotic system and sensor network applications, such as sensor coverage, search and rescue, and coverage path planning. For a truly distributed implementation of such problems, each robot should be able to compute the corresponding Voronoi cell in a distributed manner. Further, in a practical application, the robots' sensors may have limited range, thus each robot may operate within a portion of its Voronoi cell constrained by the sensor range. We describe a distributed algorithm for computation of this range constrained Voronoi cell where each robot independently constructs chords corresponding to other robots that are within a distance of twice its sensor circle radius. A robot then uses a simple and fast technique to remove inessential chords to calculate the vertices of its Voronoi cell. We prove completeness and correctness of the proposed algorithm, and also provide the upper and lower bounds on the computational complexity of our algorithm. The theoretical results are validated with the help of experiments to show that for different values of sensor ranges, our proposed algorithm incurs a time complexity that is significantly lower than that of the existing full Voronoi partition computation algorithm. The maximum number of steps required by our algorithm is also shown to be within a constant times the lower bound given by the number of neighbors of each node. © 2012 IEEE.Item Distributed, complete, multi-robot coverage of initially unknown environments using repartitioning(International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS) info@ifaamas.org, 2014) Hungerford, K.; Dasgupta, P.; Guruprasad, K.R.We consider the problem of coverage path planning by multiple robots in an environment where the location and geometry of obstacles are initially unknown to the robots. We propose a novel algorithm where the robots initially partition the environment using Voronoi partitioning. Each robot then uses an auction-based algorithm to reallocate inaccessible portions of its initial Voronoi cell to robots in neighboring Voronoi cells so that each robot is responsible for covering a set of contiguous connected regions. We have verified the performance of our algorithm on e-puck robots within the Webots simulator in different environments with different obstacle geometries and shown that it performs complete, non-overlapping coverage. © © 2014, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
- «
- 1 (current)
- 2
- 3
- »