Multi-robot belief space planning (MR-BSP) is essential for reliable and safe autonomy. While planning, each robot maintains a belief over the state of the environment and reasons how the belief would evolve in the future for different candidate actions. Yet, existing MR-BSP works have a common assumption that the beliefs of different robots are consistent at planning time. Such an assumption is often highly unrealistic, as it requires prohibitively extensive and frequent communication capabilities. In practice, each robot may have a different belief about the state of the environment. Crucially, when the beliefs of different robots are inconsistent, state-of-the-art MR-BSP approaches could result in a lack of coordination between the robots, and in general, could yield dangerous, unsafe and suboptimal decisions. In this paper, we tackle this crucial gap. We develop a novel decentralized algorithm that is guaranteed to find a consistent joint action. For a given robot, our algorithm reasons for action preferences about 1) its local information, 2) what it perceives about the reasoning of the other robot, and 3) what it perceives about the reasoning of itself perceived by the other robot. This algorithm finds a consistent joint action whenever these steps yield the same best joint action obtained by reasoning about action preferences; otherwise, it self-triggers communication between the robots. Experimental results show efficacy of our algorithm in comparison with two baseline algorithms.

Optimal placement of charging stations in a workspace is a crucial problem to address, for efficient operation of battery-driven mobile robots. When the battery charge of a robot reaches a certain threshold, the robot must be able to reach a nearby charging station to recharge its battery. In this paper, we deal with two different versions of the optimization problem related to the optimal placement of charging stations in a robot workspace. The first problem is formulated to find an optimal number of charging stations given a battery threshold deciding the need to move to a charging station, and the second problem finds an optimal battery threshold for a given number of charging stations. Both the problems involve finding the locations of charging stations, such that from any obstacle-free location at least one charging station is reachable with at most threshold amount of battery charge remaining with the robot. In this paper, we prove these optimization problems to be NP-hard, i.e., computationally intractable. To handle intractability of the above minimization problems, we design two polynomial-time approximation algorithms to find near-optimal solutions. Our algorithms achieve significantly high scalability without compromising the quality of the solution beyond a certain factor of the optimal solution. Experimental results show that our algorithms run order-of-magnitude faster than a recently proposed Satisfiability Modulo Theory (SMT)-based approach and maintain solution quality within the theoretical bounds on the optimal solution.

Efficient recharging is an essential requirement for autonomous mobile robots. In an indoor robotic application, charging stations can be installed offline. However, frequent trips to the charging stations cause inefficiency in the performance of the mobile robots. In an outdoor environment, a charging station cannot even be installed easily. We propose a framework and algorithms for enabling a group of mobile wireless rechargers to fulfill the energy requirement of autonomous mobile robots in a workspace efficiently. Our algorithm finds the optimal trajectories for the mobile rechargers in such a way that once there is a need for a recharge, the robots do not need to spend significant time and energy to get access to a recharger. Our algorithm is based on a reduction of the problems to Satisfiability Modulo Theory (SMT) solving problems. We present extensive experimental results to show that the optimal trajectories for mobile rechargers can be generated successfully for different types of robots and workspaces within a reasonable time. Moreover, a comparison with the performance of static charging stations establishes that mobile rechargers are more effective in terms of allowing the autonomous robot to continue their work for a longer time.

In many multi-robot applications, mobile worker robots are often engaged in performing some tasks repetitively by following pre-computed trajectories. As these robots are battery-powered, they need to get recharged at regular intervals. We envision that, in the future, a few mobile recharger robots will be employed to supply charge to the energy-deficient worker robots recurrently to keep the overall efficiency of the system optimized. In this setup, we need to find the time instants and locations for the meeting of the worker robots and recharger robots optimally. We present a Satisfiability Modulo Theory (SMT)-based approach that captures the activities of the robots in the form of constraints in a sufficiently long finite-length time window (hypercycle) whose repetitions provide their perpetual behavior. Our SMT encoding ensures that for a chosen length of the hypercycle, the total waiting time of the worker robots due to charge constraints is minimized under certain condition, and close to optimal when the condition does not hold. Moreover, the recharger robots follow the most energy-efficient trajectories. We show the efficacy of our approach by comparing it with another variant of the SMT-based method which is not scalable but provides an optimal solution globally, and with a greedy algorithm.

This paper presents a methodology for synthesizing a motion plan for a mobile robot to ensure that the robot never gets depleted with battery charge while carrying out its mission successfully. The specification of the robot is provided in the form of an LTL (Linear Temporal Logic) formula. A trajectory satisfying an LTL formula may contain a loop whose repetitive execution causes the depletion of battery charge in the robot. The motion plan generated by our methodology ensures that the robot visits the charging station periodically in such a way that it never gets depleted with battery charge while carrying out its mission optimally. Given a set of potential charging station locations and an LTL specification, our algorithm also finds the best location for the charging station along with the optimal trajectory for the robot. We encode the motion planning problem as an SMT (Satisfiability Modulo Theory) solving problem and use the off-the-shelf SMT solver Z3 to solve the constraints to find the location of the charging station and generate an optimal trajectory for the robot. We apply our methodology to synthesize energy-aware trajectories for robots with different dynamics in various workspaces and for various LTL specifications.

For an autonomous mobile robot, when the available power goes below a certain threshold, the robot needs to abort its current task and move towards a charging station to recharge its battery. The efficiency of an autonomous mobile robot depends significantly on the location of the charging stations. In this paper, we address the charging station placement problem for mobile robots in a controlled workspace. We propose two algorithms to place a number of charging stations so that a robot is always capable of reaching one of the charging stations from any obstacle-free location in the workspace without aborting its task too early. We reduce the charging-station placement problem to a series of Satisfiability Modulo Theory (SMT) problems and use the off-the-shelf SMT solver Z3 to implement our algorithm. The algorithm produces as output the locations of the charging stations in the workspace and the trajectories from any obstacle-free locations to one of the charging stations. Our experimental results show how our algorithm can efficiently find the locations of the charging stations and robot trajectories to reach the charging stations. We demonstrate through simulation how the generated trajectories can be effectively used by a robot to reach a charging stations autonomously without getting depleted with power.