Featured Science
Intelligent Charging Stations for Indoor Robotic Applications
Tanmoy Kundu and Indranil Saha
IIT Kanpur
Autonomous indoor robots are gradually evolving to make our lives easier. They are addressing a broader range of automation needs in factories and households. These robots are generally battery powered and require to recharge their battery at a regular interval. A robot that requires humans to constantly monitor its battery charge level and carry it to its charger whenever required cannot be fully autonomous.
Our team at IIT Kapur has found an algorithm that can help robots detect when they need recharging and then travel to the nearest charging station to get recharged.
In factories, various tasks are widely performed by autonomous robots. For instance, in Amazon Warehouse, robots are used to pick an object from one place and drop it to another place. Robots are also used for manifold domestic purposes. Take an example of the robot Roomba from i-Robot Create, which can autonomously clean a room using vacuum cleaning technology. Recent trend suggests that robots will soon find applications in commercial spaces such as hotels, hospitals, offices, banks, malls, and museums.
Detecting the power threshold
. As robots carry out manufacturing and material handling in factories they often run out of charge. Usually there are trained personnel who detect the critical level of available battery power to the robot or the power threshold and then intervene to recharge it. In a fully automated robot, whenever the battery power of the robot reaches the power threshold, the robot should abort its current task, and move towards a charging station with the remaining amount of battery charge. Different types of robots have different motion dynamics. So, different robots consume a different amount of battery power to travel the same distance. Given the power threshold and charging station locations in the workspace, the robot should be able to move autonomously towards a charging station from any location in the workspace, and with the remaining charge, it should be able to reach a charging station successfully. Now, the challenge is to decide the power threshold for a robot and place the charging station wisely to meet the above requirement. The power threshold should not be too high as in that case the robot will visit the charging station more frequently than required. On the other hand, if the power threshold is too low, it will be impossible for the robot to reach a charging station with its available charge from any location in its workspace.
Fixing the recharging location
To address the autonomous recharging problem, the robotics researchers have explored two main avenues. First, the researchers have proposed the concept of tethering the robot with some uninterrupted power supply. This, however, restricts the robot’s reachable locations heavily. The problem of entanglement of the robot with the tether may also arise. Second, some research on docking based autonomous recharging has been introduced for the robots covering a workspace with limited battery power. Their objective is to minimize the number of visits to the docking station by the robots. However, all the existing research work consider that the location of the charging station to be pre-decided.
In our work, we assume that the robot may reach its power threshold at any location in the workspace, and it should immediately move towards the closest charging station with its available charge. Therefore, the placement of charging stations can be pivotal to make the system energy-efficient.
Algorithm resolving recharging location & threshold
Charging station placement for the robot inherently depends on the parameters like power threshold, number of charging stations, and the motion dynamics of the robot. In our work, we address two variants of the charging station placement problem. In the first problem, we assume that the power threshold for the robot is given, and we aim to find the minimum number of charging stations and their locations. In the second problem, we assume that the number of charging stations to be installed is given, and we attempt to find their locations and the value of the minimum power threshold for the robots.
In our approach, we reduce the above two problems into optimization problems. In the first problem, the power threshold is given, and we find the minimum number of charging stations required to serve the robots and their locations. The second variant considers the number of charging stations to be given, and we findtheir locations and the value of the minimum power threshold. Note that in both the cases the charging stations are placed in a way that the robots can reach a charging station from any obstacle-free location in the workspace, with the amount of energy remaining with the robot being greater than or equal to the power threshold.
Our search for the algorithm
Our proposed algorithms to solve both the variants of the problem are similar. Let us consider the first problem variant to explain the proposed algorithmic procedure. In this problem, our objective is to minimize the number of charging stations. We reduce this optimization problem to a series of constraint solving problem. For each such constraint solving problem, we choose a value for the number of charging stations. If the set of constraints has a solution, it implies that the number of charging stations can be the current value chosen for it.
The decision variables in these constraints are the location of the charging stations and a motion plan for the robot from each location in the workspace to one of the charging stations. Constraints for the above problem are related to the workspace description, obstacles, robot motion dynamics, and power threshold. For example, a set of constraints can be introduced to ensure the following - from any obstacle-free location in the workspace, there exists a trajectory to one of the charging station locations, and the trajectory does not require more power than the power threshold. In a naive approach, we can simply check the satisfiability of the above-mentioned set of constraints starting from a small value for the number of charging stations. With every test value for the number of charging stations, we check for satisfiability of all the constraints. If a solution for the constraints does not exist, we check the constraints for the immediate next value for the number of charging stations, and we keep increasing the number of charging stations until we obtain a solution for the constraints.
A solution of the constraints provides the required number of charging stations along with their locations. This approach is guaranteed to give a solution on its termination. However, as this naïve procedure requires to check for a solution to a large set of constraints for every number of charging stations until we get a solution, it suffers from the lack of scalability, and solving the problem for a large workspace requires an exorbitant amount of time.
Whenever the set of constraints is unsatisfiable for a chosen power threshold, there exists a set of locations in the workspace from where the robot cannot reach a charging station with the energy equivalent to the threshold. We propose a novel algorithm where we identify this set of locations and attempt to solve the constraints for the next higher value for the number of charging stations to satisfy only this set of locations. This leads to solving a much smaller set of constraints. If the set of constraints is not satisfiable, we try the next larger value for the number of charging stations. In any iteration, if this new set of constraints is satisfiable, it means that the locations that could not be served in the previous iteration where we tried to cover all the locations in the workspace can be served now.
However, the locations of charging stations may not be convenient for some other locations in the workspace. So, we need to test the satisfiability of the solution with the original set of constraints that covers all the locations. We may or may not get a satisfiable solution this time. If we get a solution for the constraints, we have been able to solve the problem entirely and found the minimum number of charging stations and their locations that cover all the locations in the workspace. Otherwise, it implies that the solution obtained for the smaller subset of the locations is not suitable for all the locations in the workspace. We now find a new subset of locations from which there does not exist a path to a charging station location and repeat the procedure. The procedure goes on iteratively until we get a solution satisfying all the locations in the workspace.
In summary, in every iteration, instead of checking the constraints for all the locations in the workspace, our algorithm formulates the constraints for the locations which cannot be served with the chosen number of charging stations. Then it intelligently checks the usability of the solution from the perspective of all the locations. This makes our algorithm scalable to a larger size of the workspace. Our approach also guarantees an optimal solution to the problem.
Software Tool we used
In our experiments, we use Z3 SMT (Satisfiability Modulo Theory) solver from Microsoft research as the backend constraint solver. An SMT solver can solve a complex set of constraints efficiently. An advantage of using an SMT solver in implementing our algorithm is that whenever the solver cannot find a solution for a set of constraints, it finds a small subset of the constraints that itself is unsatisfiable. This small subset is called the unsatisfiable core (aka unsat-core) of the original set of constraints. By using an unsat-core produced by the SMT solver, we can effectively find a subset of locations for which there does not exist a trajectory to a charging station.
We have carried out experiments with three different types of robots – a Turtlebot, a quadcopter, and a Dubins car; in three different types of workspaces, like a warehouse, an artificial floor, and a maze; and two different dimensions for each of the workspaces. In almost all the cases, our proposed approach turns out to be much more scalable compared to the naive solution. The experiment shows that our algorithm for both the problems run 30-85% faster compared to their naive counterparts. The figure shows an example of charging station placement using our algorithm. We solved the first problem variant to find the minimum number of charging stations for different robots. Power threshold is kept constant to 7, meaning that the robot should be able to reach a charging station within seven steps. The figure shows the placement of charging stations in a Warehouse-like workspace.
Our algorithms provide an optimal solution in terms of the number of charging station (for the first problem), the power threshold (for the second problem) and the motion plans (for both variants) to move from any obstacle-free location to one of the charging stations. The problem we address here is a version of the famous facility location problem. However, to the best of our knowledge, this work is the first one to take into account the complex dynamics of the robots while planning facility locations for them in a workspace. We are currently extending this work by co-synthesizing the trajectory of a robot with a specific perpetual mission and the location of the charging stations.
