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.

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.

This paper addresses the problem of automated multiagent search in an unknown environment. Autonomous agents equipped with sensors carry out a search operation in a search space, where the uncertainty, or lack of information about the environment, is known a priori as an uncertainty density distribution function. The agents are deployed in the search space to maximize single step search effectiveness. The centroidal Voronoi configuration, which achieves a locally optimal deployment, forms the basis for the proposed sequential deploy and search strategy. It is shown that with the proposed control law the agent trajectories converge in a globally asymptotic manner to the centroidal Voronoi configuration. Simulation experiments are provided to validate the strategy.

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.