MOSAIC schedulers

Author

Federico Rossi, Tiago Stegun Vaquero, Joshua Vander Hook

Address

4800 Oak Grove Dr. Pasadena, CA 91109

Contact

federico.rossi@jpl.nasa.gov, tiago.stegun.vaquero@jpl.nasa.gov, hook@jpl.nasa.gov

Organization

Jet Propulsion Laboratory (JPL)

Release

2.0.0

Repository

https://github.com/nasa/mosaic

Abstract

Communication-aware dynamic task allocation in multi-robot systems

Introduction

MOSAIC provides scheduling tools to allocate computational tasks to robots with heterogeneous computational capabilities and time-varying communication links.

This package contains three+1 scheduling and task allocation algorithm.

• Time-varying scheduling algorithm (tv_milp). A mixed-integer programming algorithm for scheduling tasks in heterogeneous robotic networks with time-varying communication links. The scheduler can accommodate any non-cyclical dependencies between tasks and arbitrary time-varying communication links, handle optional tasks with associated rewards, and optimize cost functions including rewards for optional tasks, makespan, and energy usage. The scheduler is presented in [1].

• Task allocation algorithm for robotic networks with periodic connectivity (ti_milp). A mixed-integer programming algorithm for task allocation in heterogeneous robotic networks with periodic communication links. The task allocation algorithm also accommodates any non-cyclical dependencies between tasks and handles optional tasks with associated rewards and maximum latency requirements; it can maximize reward from optional tasks or minimize energy use. The task allocation algorithm is presented in [2].

• For benchmarking purposes, we also provide a lightly modified version of Topcuoglu, Hariri, and Wu’s Heterogeneous Earliest Finish Time (HEFT) algorithm (heft).

• A scheduling algorithm (ti_milp_heft) that uses the proposed task allocation algorithm to assign tasks to agents, and HEFT (with fixed task allocation) to schedule task execution.

For a full description of the algorithm, we refer the interested reader to our papers.

Contents

• 1. Installation
  • 1.1. Requirements
  • 1.2. Installation
  • 1.3. Docker
• 2. Time-varying scheduling algorithm
  • 2.1. Problem Description
  • 2.2. ILP formulation
  • 2.3. Implementation
  • 2.4. References
• 3. Task allocation algorithm for robotic networks with periodic connectivity
  • 3.1. Problem Parameters
  • 3.2. Optimization Variables
  • 3.3. Optimization Objective
  • 3.4. Problem Formulation
  • 3.5. Implementation
  • 3.6. References
• 4. Usage Examples
  • 4.1. Create a problem instance
  • 4.2. Solve with a time-varying MILP solver
  • 4.3. Allocate tasks with a “time-invariant” solver
  • 4.4. Selfish agents
  • 4.5. Node Assist
  • 4.6. Base Station Assist
  • 4.7. Assembly Line
• 5. API reference
  • 5.1. Input format
  • 5.2. Output format
• 6. Modules documentation
  • 6.1. Time-varying scheduling algorithm: full implementation
  • 6.2. Task allocation algorithm for robotic networks with periodic connectivity: full implementation

Copyright and Licensing

Copyright (c) 2020, California Institute of Technology (“Caltech”). U.S. Government sponsorship acknowledged.

mosaic-schedulers is currently an open-source package distributed under the Apache 2.0 license.

References

[1] Joshua Vander Hook, Tiago Vaquero, Federico Rossi, Martina Troesch, Marc Sanchez Net, Joshua Schoolcraft, Jean-Pierre de la Croix, and Steve Chien, “Mars On-Site Shared Analytics Information and Computing,” in Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, vol. 29, no. 1, pp. 707-715, July 2019.

[2] Federico Rossi*, Tiago Stegun Vaquero*, Marc Sanchez Net, Maíra Saboia da Silva, and Joshua Vander Hook, “The Pluggable Distributed Resource Allocator (PDRA): a Middleware for Distributed Computing in Mobile Robotic Networks,” under review.

[3] H. Topcuoglu, S. Hariri and Min-You Wu, “Performance-effective and low-complexity task scheduling for heterogeneous computing,” in IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 3, pp. 260-274, March 2002.

Indices and tables

• Index

• Module Index

• Search Page