README.md

Multi-Robot Task Allocation (MRTA) for e-Warehouses

Overview

The objective of this project is to generate an optimal tasking schedule for robots in a warehouse environment, minimizing overall operational costs. The warehouse layout includes feeder belts that supply load packages to autonomously operated mobile robots, which then transport them to designated storage units. Robots follow pre-assigned lanes with known speeds, and their battery discharge is modeled based on task load and travel distance. Recharging stations ensure that robots remain operational.

Problem Formulation

The warehouse environment is represented as a graph:

• Vertices (V):
  • VF: Feeder nodes (where loads originate)
  • VU: Unit nodes (load drop-off locations)
  • VJ: Junction nodes (connecting multiple lanes)
• Edges (E):
  • EU: Low-speed tracks (connecting aisles and units)
  • EA: Medium-speed tracks (along aisles)
  • ES: High-speed tracks (priority lanes)

Robot and Load Definitions

Each robot $ R_i $ is defined as:

• $ R_i := { B_i, D_i } $
  • $ B_i $: Battery level
  • $ D_i $: Discharge factor (rate of battery depletion based on load weight and distance traveled)

Each load $ L_j $ is defined as:

• $ L_j := { W_j, VP_j, VD_j } $
  • $ W_j $: Load weight
  • $ VP_j $: Pickup node
  • $ VD_j $: Drop-off node

A task $ T_k $ is assigned as:

• $ T_k := { L_j, R_i } $

Optimization Objective

The MRTA problem seeks to minimize the following cost function: $$ \min \sum_{t=T_1}^{T_\tau} (w_1 E_t + w_2 S_t) + w_3 I $$ where:

• $ \tau $ = total number of tasks
• $ E_t $ = energy expended during a task
• $ S_t $ = task completion time
• $ I $ = workload imbalance among robots
• $ w_1, w_2, w_3 $ = tuning weights

Constraints

1. All tasks must be completed.
2. A robot cannot operate below 15% battery and must recharge when reaching this threshold.

Solution Approach

Since MRTA is an NP-hard combinatorial problem, Discrete Adaptive Particle Swarm Optimization (DAPSO) to optimize the task allocation and scheduling process.

Methodology

Classical PSO is designed for optimizing the cost function in a continuous $ n $-dimensional space where the particles move by updating their velocities. This update depends on each particle’s cognitive learning as well as the information sourced from its neighbors. The general update rule is given by:

$$ v_p^{t+1} = \omega v_p^t + c_1 r_1 (pBest_p^t - x_p^t) + c_2 r_2 (gBest_p^t - x_p^t) $$

$$ x_p^{t+1} = x_p^t + v_p^{t+1} $$

where:

• $ v_p^t $ and $ x_p^t $ are the velocity and position of particle $ p $ at time $ t $, respectively.
• $ \omega $ is the inertia weight controlling the influence of the previous velocity.
• $ c_1 $ and $ c_2 $ are acceleration coefficients that control the impact of cognitive and social learning, respectively.
• $ r_1 $ and $ r_2 $ are random numbers uniformly distributed in $ [0,1] $.
• $ pBest_p^t $ is the best position found by particle $ p $ so far.
• $ gBest_p^t $ is the best global position found by any particle in the swarm.

The adaptation of classical PSO to a discrete combinatorial problem requires redefining the velocity and position update rule.

For the MRTA problem, we define the entire task allocation sequence as the position of a particle. The velocity update is based on discrete crossovers. After every iteration, the particle updates its velocity and position based on the following rule:

$$ v_p^{t+1}[k] = \begin{cases} 1, & \text{if } r_n < c_n \\ 0, & \text{otherwise} \end{cases} $$

$$ x_p^{t+1}[k] = \begin{cases} x_{best}^t[k], & \text{if } v_p^{t+1}[k] = 1 \\ x_{rand}^t, & \text{otherwise} \end{cases} $$

where:

• $ x_{best}^t[k] $ is the $ k $-th task in the task queue for the best particle.
• $ x_{rand}^t $ is a random task generated by choosing any robot.
• $ c_n $ is a crossover probability threshold.
• $ r_n $ is a randomly generated number in $ [0,1] $.

We control the maximum number of crossovers in the task schedule to prevent exploitation in the early stage of the simulation. Take a look at mrta.ipynb for the full implementation.

Contributors

• Sachin Verma
• Raj Vijayaraj
• Iris Uwizeyimana

References

[1] A. Agrawal, A. S. Bedi, and D. Manocha, "Rtaw: An attention inspired reinforcement learning method for multi-robot task allocation in warehouse environments," arXiv preprint arXiv:2209.05738, 2022. [2] C. Akjiratikarl, P. Yenradee, and P. R. Drake, "Pso-based algorithm for home care worker scheduling in the uk," Computers Industrial Engineering, vol. 53, pp. 559–583, 2007. [3] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba, "Openai gym," arXiv preprint arXiv:1606.01540, 2016. [4] P. O. Dusadeerungsikul, X. He, M. Sreeram, and S. Y. Nof, "Multi-agent system optimisation in factories of the future: cyber collaborative warehouse study," International Journal of Production Research, vol. 60, no. 20, pp. 6072–6086, 2022. [5] K. Jose and D. K. Pratihar, "Task allocation and collision-free path planning of centralized multi-robots system for industrial plant inspection using heuristic methods," Robotics and Autonomous Systems, vol. 80, pp. 34–42, 2016. [6] A. Khamis, A. Hussein, and A. Elmogy, "Multi-robot task allocation: A review of the state-of-the-art," Cooperative robots and sensor networks 2015, pp. 31–51, 2015. [7] D. K. Liu and A. K. Kulatunga, Simultaneous Planning and Scheduling for Multi-Autonomous Vehicles. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 437–464. [8] A. Raffin, A. Hill, M. Ernestus, A. Gleave, A. Kanervisto, and N. Dormann, "Stable baselines3," 2019. [9] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, "Proximal policy optimization algorithms," arXiv preprint arXiv:1707.06347, 2017. [10] J. Yu and S. M. LaValle, "Optimal multirobot path planning on graphs: Complete algorithms and effective heuristics," IEEE Transactions on Robotics, vol. 32, no. 5, pp. 1163–1177, 2016.