6. Modules documentation

6.1. Time-varying scheduling algorithm: full implementation

A module that implements the MOSAIC MILP scheduling algorithm.

class mosaic_schedulers.schedulers.tv_milp.MOSAICSolver.MILPTasks(OptionalTasks={}, TaskReward={}, ProductsSize={}, DependencyList={}, IncompatibleTasks={})

A class containing a representation of the tasks for the MILP scheduler.

Parameters

• OptionalTasks (list) – a dict with Tasks as keys. OptionalTasks[Task] is True if Task is optional and False otherwise.

• TaskReward – a dict with Tasks as keys. TaskReward[Task] is the reward obtained for completing Task, a float.

• ProductsSize (dict) – a dict with Tasks as keys. PS[Task] is the size of the products of Task (in storage units), a float.

• DependencyList (dict) – a dict with Tasks as keys. DL[Task] expresses the pre-requisites for each Task is conjunctive normal form. That is, DependencyList[Task] is a list. Each entry of the List contains a number of predecessor Tasks. For each entry in DependencyList[Task][i], at least one task must be performed.

• OptionalTasks – a list of lists. IT[j] is a list of tasks that are incompatible with each other (that is, only one can be executed).

class mosaic_schedulers.schedulers.tv_milp.MOSAICSolver.MILPAgentCapabilities(ComputationTime={}, ComputationLoad={}, InitialInformation={}, EnergyCost={}, CommEnergyCost={})

A class containing a representation of the agent capabilities for the MILP scheduler.

Parameters

• ComputationTime (dict) – a dictionary with keys Task, Agent. The value of CT[Task][Agent] is the time (in time steps) required for Agent to complete Tasks, an int.

• ComputationLoad (dict) – a dictionary with keys Task, Agent. The value of CT[Task][Agent] is the fraction of Agent’s computational resources required to complete Task, a float between 0 and 1.

• InitialInformation (dict) – a dictionary with keys Task, Agent. II[Task][Agent] is a Bool. It is true iff Agent knows the output of Task at time t=0. This can be helpful to specify that only one agent can do a given task

• EnergyCost (bool) – a dictionary with keys Task, Agent. EnergyCost[T][A] is the energy cost when agent A computes task T.

• CommEnergyCost (bool) – a dictionary witk keys Time, Sender, Receiver. CET[t][i][j] is the energy cost to send one bit of information from i to j at time t. The actual energy cost is computed as CET[t][i][j]*Bandwidth[t][i][j]* *sum_m C[i][j][m][t]

class mosaic_schedulers.schedulers.tv_milp.MOSAICSolver.CommunicationNetwork(CommWindowsBandwidth={}, CommEnergyCost=None)

A class containing a representation of the communication network.

Parameters

• CommWindowsBandwidth (dict) – a collection of communication windows. CommWindows is a dictionary with keys [0…Thor-1], [Agent], [Agent]. CommWindows[Time][Agent1][Agent2] is the bandwidth available to communicate between Agent1 and Agent2 at Time (in bits per unit time).

• CommEnergyCost (dict) – a dictionary witk keys Time, Sender, Receiver. CET[t][i][j] is the energy cost to send one bit of information from i to j at time t. The actual energy cost is computed as CET[t][i][j]*Bandwidth[t][i][j]*sum_m C[i][j][m][t]

class mosaic_schedulers.schedulers.tv_milp.MOSAICSolver.JSONSolver(JSONProblemDescription='', solver='CPLEX', Verbose=False, TimeLimit=None)

The main interface to solve MOSAIC scheduling problems

Parameters

• JSONProblemDescription (str, optional) – a JSON description of the problem. See the API reference for a detailed description. Defaults to ‘’

• solver (str, optional) – the solver to use. Should be ‘GLPK’, ‘CPLEX’, ‘PuLP’ or ‘SCIP’, defaults to ‘CPLEX’

• Verbose (bool, optional) – whether to print status and debug messages. Defaults to False

• TimeLimit (float, optional) – a time limit after which to stop the optimizer. Defaults to None (no time limit). Note that certain solvers (GLPK) may not honor the time limit.

Raises

ValueError – if the JSONProblemDescription is not valid.

class mosaic_schedulers.schedulers.tv_milp.MOSAICSolver.MOSAICMILPScheduler(Thor, AgentCapabilities, Tasks, CommunicationNetwork, TimeStep, Options={}, Verbose=False)

Warning

For an easier-to-use and more consistent interface, you most likely want to call JSONSolver instead of this class and its subclasses.

Abstract implementation of a MILP solution to the MOSAIC scheduler. Subclassed by the solvers MOSAICCPLEXScheduler, MOSAICSCIPScheduler, MOSAICPULPScheduler, and MOSAICGLPKScheduler. You probably want to call JSONSolver instead of these.

Usage:

• schedule(): creates the optimization problem, solves it, and returns a JSON representation of the solution (in non-standard format)

• getOptimizationTerminator(): returns a function that can be called to stop the optimization process asynchronously

For a detailed description of the MILP problem we solve, see the IJRR manuscript.

Parameters

• Thor (int) – the time horizon of the optimization, an int.

• AgentCapabilities (MOSAICSolver.MILPAgentCapabilities) – detailing what the agents can do

• Tasks (MOSAICSolver.MILPTasks) – detailing the tasks that must be achieved

• CommunicationNetwork (MOSAICSolver.CommunicationNetwork) – detailing the communication network availability

• TimeStep (float) – The duration (in seconds) of a discrete time step.

• Options (dict, optional) – additional solver-specific options, defaults to {}

• Verbose (bool, optional) – if True, prints status and debug messages. Defaults to False

solverSpecificInit()

A place to define solver-specific initializations in subclasses

formatOutput(version=2)

Formats output.

Parameters

version (int, optional) – V1: just a pass-through for formatToJSON. V2 (default): the standard I/O format defined in the API reference.

Returns

JSON output

Return type

str

getRawOutput()

Return the raw problem output from the solver

schedule()

Set up the problem, solve it, and return the solution (in an older, non-JSON I/O format)

setTimeLimits(DetTicksLimit, ClockTimeLimit)

Sets a time limit for the overall process. May be ignored by certain solvers.

setSolverParameters(Properties)

Passes a dictionary of parameters to the solver

setUp()

The problem is set up here. At this time, the entire setup is repeated for each solver.

solve()

The problem is solved here.

setMIPStart(MIPStart)

Certain solvers allow the MIP to be “seeded” with a MIP start.

getSolverState()

This function allows extracting the internal MIP state for warm-starting.

getProblem()

Return the solver-specific problem object

getOptimizationTerminator()

Gets an object that can be called to stop the optimization process

class mosaic_schedulers.schedulers.tv_milp.MOSAICSolver.MOSAICCPLEXScheduler(Thor, AgentCapabilities, Tasks, CommunicationNetwork, TimeStep, Options={}, Verbose=False)

An implementation of the MILP scheduler that uses the IBM ILOG CPLEX solver.

solverSpecificInit()

A place to define solver-specific initializations in subclasses

setUp()

The problem is set up here. At this time, the entire setup is repeated for each solver.

solve()

The problem is solved here.

setMIPStart(MIPStart, effort_level=0)

Certain solvers allow the MIP to be “seeded” with a MIP start.

schedule()

Set up the problem, solve it, and return the solution (in an older, non-JSON I/O format)

getSolverState()

This function allows extracting the internal MIP state for warm-starting.

getProblem()

Return the solver-specific problem object

getOptimizationTerminator()

Gets an object that can be called to stop the optimization process. To actually terminate the problem, call the method abort() of the returned object.

setTimeLimits(DetTicksLimit=1e+75, ClockTimeLimit=1e+75)

Sets a time limit for the overall process. May be ignored by certain solvers.

setSolverParameters(Properties)

Passes a dictionary of parameters to the solver

class mosaic_schedulers.schedulers.tv_milp.MOSAICSolver.MOSAICSCIPScheduler(Thor, AgentCapabilities, Tasks, CommunicationNetwork, TimeStep, Options={}, Verbose=False)

An implementation of the MILP scheduler that uses the SCIP solver.

solverSpecificInit()

A place to define solver-specific initializations in subclasses

setUp()

The problem is set up here. At this time, the entire setup is repeated for each solver.

solve()

The problem is solved here.

setMIPStart(MIPStart)

Certain solvers allow the MIP to be “seeded” with a MIP start.

schedule()

Set up the problem, solve it, and return the solution (in an older, non-JSON I/O format)

getSolverState()

This function allows extracting the internal MIP state for warm-starting.

getProblem()

Return the solver-specific problem object

setTimeLimits(DetTicksLimit=None, ClockTimeLimit=None)

Sets a time limit for the overall process. May be ignored by certain solvers.

setSolverParameters(Properties)

Passes a dictionary of parameters to the solver

class mosaic_schedulers.schedulers.tv_milp.MOSAICSolver.MOSAICPULPScheduler(Thor, AgentCapabilities, Tasks, CommunicationNetwork, TimeStep, Options={}, Verbose=False)

An implementation of the MILP scheduler that uses the PuLP modeling package.

solverSpecificInit()

A place to define solver-specific initializations in subclasses

setUp()

The problem is set up here. At this time, the entire setup is repeated for each solver.

solve()

The problem is solved here.

getSolverState()

This function allows extracting the internal MIP state for warm-starting.

getProblem()

Return the solver-specific problem object

class mosaic_schedulers.schedulers.tv_milp.MOSAICSolver.MOSAICGLPKScheduler(Thor, AgentCapabilities, Tasks, CommunicationNetwork, TimeStep, Options={}, Verbose=False)

An implementation of the MILP scheduler that uses the GLPK solver.

solverSpecificInit()

A place to define solver-specific initializations in subclasses

setUp()

The problem is set up here. At this time, the entire setup is repeated for each solver.

solve()

The problem is solved here.

schedule()

Set up the problem, solve it, and return the solution (in an older, non-JSON I/O format)

getSolverState()

This function allows extracting the internal MIP state for warm-starting.

getProblem()

Return the solver-specific problem object

setTimeLimits(DetTicksLimit=1e+75, ClockTimeLimit=1e+75)

Sets a time limit for the overall process. May be ignored by certain solvers.

setSolverParameters(Properties)

Passes a dictionary of parameters to the solver

6.2. Task allocation algorithm for robotic networks with periodic connectivity: full implementation

The module ti_milp provides an implementation of the task allocation algorithm for for robotic networks with periodic connectivity.

class mosaic_schedulers.schedulers.ti_milp.MOSAICTISolver.MILPTasks(OptionalTasks={}, TaskReward={}, ProductsBandwidth={}, ProductsDataSize={}, DependencyList={}, MaxLatency={})

A class containing a representation of the tasks for the MILP scheduler.

Parameters

• OptionalTasks (dict) – a dict with Tasks as keys. OT[Task] is True iff the task is optional.

• TaskReward (dict) – a dict with Tasks as keys. TR[Task] is the reward obtained for performing the task, a float.

• ProductsBandwidth (dict) – a dict with Tasks as keys. PB[Task] is the bandwidth required to stream of the products of Task (in storage units per time units), a float.

• ProductsDataSize (dict) – a dict with Tasks as keys. PDS[Task] is the size of the products of Task (in storage units), a float.

• DependencyList (dict) – a dict with Tasks as keys. DL[Task] is a list of tasks whose data products are required to compute Task.

• MaxLatency (dict) – a dict with keys task1, task2. MaxLatency[T1][T2] is the maximum latency that the data products of T2 (a dependency of T1) can tolerate before they are ingested by task T1.

validate()

Ensure the Tasks structure is valid, i.e. the keys to the various components are consistent

class mosaic_schedulers.schedulers.ti_milp.MOSAICTISolver.MILPAgentCapabilities(ComputationLoad={}, EnergyCost={}, MaxComputationLoad={}, LinkComputationalLoadIn={}, LinkComputationalLoadOut={})

A class containing a representation of the agent capabilities for the MILP scheduler.

Parameters

• ComputationLoad (dict) – a dictionary with keys Agent, Task. The value of ComputationLoad[Agent][Task] is the amount of Agent’s computational resources required to complete Task.

• EnergyCost (dict) – a dictionary with keys Agent, Task. EnergyCost[A][T] is the energy cost when agent A computes task T.

• MaxComputationLoad (dict) – a dict with keys Agents. MaxComputationLoad[A] is the maximum computational resources of agent A.

• LinkComputationalLoadIn (dict) – a dict with keys Agent, Agent. LinkComputationalLoadIn[A1][A2] is the computational load required to decode messages on link [A1][A2] at A2.

• LinkComputationalLoadOut (dict) – a dict with keys Agent, Agent. LinkComputationalLoadOut[A1][A2] is the computational load required to encode messages on link [A1][A2] at A1.

class mosaic_schedulers.schedulers.ti_milp.MOSAICTISolver.CommunicationNetwork(Bandwidth={}, Latency={}, EnergyCost={})

A class containing the properties of the communication network used by the time-invariant scheduler.

Parameters

• Bandwidth (dict) – a dictionary with keys Agent, Agent. Bandwidth[A1][A2] is the bandwidth from agent A1 to agent A2. If Bandwidth[A1][A2] is zero, the link is not considered in the optimization problem.

• Latency (dict) – a dictionary with keys Agent, Agent. Latency[A1][A2] is the latency of the link. Note that the latency of a datagram should be (but isn’t at this time) computed as Latency[A1][A2] + datagram_size/Bandwidth[A1][A2].

• EnergyCost (dict) – a dictionary with keys Agent, Agent. EnergyCost[A1][A2] is the energy cost to transmit one bit on link A1-A2. The actual energy cost is computed as EnergyCost[A1][A2]*bit_rate[A1][A2].

class mosaic_schedulers.schedulers.ti_milp.MOSAICTISolver.JSONSolver(JSONProblemDescription, Verbose=False, solver='GLPK', TimeLimit=None)

Creates an instance of the time-invariant problem based on a problem input in the format described in the API reference.

Parameters

• JSONProblemDescription (str, optional) – a JSON description of the problem. See the API reference for a detailed description.

• Verbose (bool, optional) – whether to print status and debug messages. Defaults to False

• solver (str, optional) – the solver to use. Should be ‘GLPK’, ‘CPLEX’, or ‘SCIP’, defaults to ‘GLPK’.

• TimeLimit (float, optional) – a time limit after which to stop the optimizer. Defaults to None (no time limit). Note that certain solvers (in particular, GLPK) may not honor the time limit.

Raises

AssertionError – if the JSONProblemDescription is not valid.

Warning

This solver does not support disjunctive prerequirements (do this task OR that task). If a problem with disjunctive prerequirement is passed, the solver will assert.

schedule()

Solve the scheduling problem.

Returns

A solution in the JSON format described in the API reference.

Return type

str

class mosaic_schedulers.schedulers.ti_milp.MOSAICTISolver.MOSAICMILPSolver(AgentCapabilities, Tasks, CommunicationNetwork, Options={}, Verbose=False)

Warning

For an easier-to-use and more consistent interface, you most likely want to call JSONSolver instead of this class and its subclasses.

Abstract implementation of the MILP task allocator. Subclassed by MOSAICCPLEXSolver, MOSAICSCIPSolver, and MOSAICGLPKSolver.

Parameters

• AgentCapabilities (MOSAICTISolver.MILPAgentCapabilities) – detailing what the agents can do

• Tasks (MOSAICTISolver.MILPTasks) – detailing the tasks that must be achieved

• CommunicationNetwork (MOSAICTISolver.CommunicationNetwork) – detailing the communication network availability

• Options (dict, optional) – additional solver-specific options, defaults to {}

• Verbose (bool, optional) – if True, prints status and debug messages. Defaults to False

solverSpecificInit()

A place to define solver-specific initializations in subclasses

getRawOutput()

Return raw problem output from the scheduler

schedule()

Set up and solve the scheduling problem

setTimeLimits(DetTicksLimit=1e+75, ClockTimeLimit=1e+75)

Sets a time limit for the overall process. May be ignored by certain solvers.

setSolverParameters(Properties)

Passes a dictionary of parameters to the solver

setUp()

Set up the optimization problem. Solver-specific.

solve()

Solve the optimization problem. Solver-specific.

setMIPStart(MIPStart)

Provide a warm start to the solver. Solver-specific.

getSolverState()

Get the solver state. Solver-specific.

getProblem()

Get the solver problem object.

getOptimizationTerminator()

Gets an object that can be called to stop the optimization process

formatToBenchmarkIO()

Formats the scheduler output to the JSON format described in the API reference

class mosaic_schedulers.schedulers.ti_milp.MOSAICTISolver.MOSAICCPLEXSolver(AgentCapabilities, Tasks, CommunicationNetwork, Options={}, Verbose=False)

A dummy implementation of the MILP scheduler if CPLEX is not available.

solverSpecificInit()

A place to define solver-specific initializations in subclasses

class mosaic_schedulers.schedulers.ti_milp.MOSAICTISolver.MOSAICGLPKSolver(AgentCapabilities, Tasks, CommunicationNetwork, Options={}, Verbose=False)

An implementation of the MILP scheduler that uses the GLPK solver.

solverSpecificInit()

A place to define solver-specific initializations in subclasses

setUp()

Set up the optimization problem. Solver-specific.

solve()

Solve the optimization problem. Solver-specific.

schedule()

Set up and solve the scheduling problem

getSolverState()

Get the solver state. Solver-specific.

getProblem()

Get the solver problem object.

setTimeLimits(DetTicksLimit=1e+75, ClockTimeLimit=1e+75)

Sets a time limit for the overall process. May be ignored by certain solvers.

class mosaic_schedulers.schedulers.ti_milp.MOSAICTISolver.MOSAICSCIPSolver(AgentCapabilities, Tasks, CommunicationNetwork, Options={}, Verbose=False)

An implementation of the MILP scheduler that uses the SCIP solver.

solverSpecificInit()

A place to define solver-specific initializations in subclasses

setUp()

Set up the optimization problem. Solver-specific.

solve()

Solve the optimization problem. Solver-specific.

schedule()

Set up and solve the scheduling problem

getSolverState()

Get the solver state. Solver-specific.

getProblem()

Get the solver problem object.

setTimeLimits(DetTicksLimit=None, ClockTimeLimit=None)

Sets a time limit for the overall process. May be ignored by certain solvers.

setSolverParameters(Properties)

Passes a dictionary of parameters to the solver