Scheduling the Refuelling Activities of Multiple Heterogeneous Autonomous Mobile Robots

Scheduling the Refuelling Activities of Multiple Heterogeneous Autonomous Mobile Robots

Huisman, R.

Keviczky, T. (mentor)

Mechanical, Maritime and Materials Engineering

Delft Center for Systems and Control

Systems and Control

2014-10-30

When a team of autonomous mobile robots (MRs) has to perform a mission of a duration that exceeds their energy capacities, the mission can only be fulfilled if the MRs are resupplied. Nowadays most MRs are powered by batteries, which can either be recharged, or replaced. Since it is not necessary that the MRs are battery powered, we will use the general term refuelling instead of recharging. In general there are two options for MRs to refuel themselves: by travelling to a fuelling station (FS) that is situated at a fixed location, or rendezvousing with a mobile fuelling station (MFS). When multiple MRs operate in the same environment, it is desired that the MRs share the available FSs instead of each MR having its own dedicated FS. Sharing the FSs will reduce the purchase and maintenance costs, and less space will be needed for the placement of FSs. The FSs considered during this thesis, can only refuel a single robot at a time. This raises the need for properly scheduling the refuelling activities, such that the FSs are shared in an efficient manner, and depletion of the MRs can be prevented. This thesis presents several methods to schedule the refuelling activities of multiple heterogeneous autonomous MRs. The scheduling is focused on the selection of the refuel events, and the allocation of the FSs as a shared resource. The following problem is considered: For an environment which contains an arbitrary number of FSs, and MRs, the refuelling activities should be scheduled in such a way that the overall mission time is minimized. Each mission entails an assignment of a unique set of waypoints for each MR which have to be visited in a pre-determined order, in order to complete the mission. The total mission is accomplished when the last MR is completely refuelled, after visiting its last waypoint. Scheduling the refuelling activities using a time-based metric is complicated compared to a distance-based metric. Since a FS can refuel only a single MR at a time, the duration that each MR spends refuelling, and the ordering in which the MRs are refuelling have to be taken into account. Furthermore since the MRs share the FSs, each refuel event of one MR can affect all future refuel events of all other MRs. Global optimal solutions for this problem can be found by using a centralized approach as shown in this thesis. However, since all refuel events of all MRs can influence each other, the complexity increases very quickly when the problem size increases. In order to obtain a global optimum, all possible refuel events have to be taken into account. Due to the computational complexity, the problem size that can be solved by this approach is limited. In order to solve larger scale problems, a trade-off has been made between computation time and solution quality. A distributed, and hierarchical architecture are proposed, in order to distribute the computations and decision making over the robotic team. The core of the distributed approach is that MRs make individual decisions based on local knowledge. The decision making of the hierarchical approach is done for individuals or clusters of MRs. Simulation case studies indicate that these decentralized approaches can be used to solve large scale problems in real-time, at the cost of a suboptimal solution.

mobile robot
autonomous
scheduling
refuelling

http://resolver.tudelft.nl/uuid:9bedd086-c4e6-4824-83f7-6e9805e63579

Student theses

master thesis

(c) 2014 Huisman, R.