examples.agent_assignment package

This folder contains the implementation of the sample experiment that explores the performance of the B&B algorithm for solving the agent assignment problem.

Submodules

examples.agent_assignment.bnb module

The implementation of the Branch and Bound (B&B) algorithm.

class Option

Bases: object

The options determining the B&B variant.

NO_CUTOFFS = 'No cutoffs'

If Option.NO_CUTOFFS is specified, the B&B cutoffs will not be performed.

HEURISTIC = 'Heuristic'

If Option.HEURISTIC is specified, B&B will use the heuristic.

assignment2str(assignment: AgentAssignment) → str

Translate the agent assignment to string.

Parameters:

assignment (AgentAssignment) – An (partial) agent assignment.

Returns:

The string representation of the agent assignment.

Return type:

str

class Algorithm

Bases: object

The class representing the B&B algorithm.

__init__(options: set, instance: ProblemInstance)

The constructor.

Parameters:

  • options (set) – The options controlling the behaviour of the algorithm.

  • instance (ProblemInstance) – The problem instance

result_titles() → Tuple[str]

Names of quantities in the result tuple.

Returns:

Names of quantities in the result tuple.

Return type:

Tuple[str]

search() → tuple

Performs B&B search to solve the problem instance.

Returns:

The results of the search.

Return type:

tuple

Performs B&B search to solve the problem instance. This method is called by search and should not be called directly.

Parameters:

  • assignment (AgentAssignment) – The current parial assignment.

  • g (float) – The time used for completion of the tasks in assignment.

_full_assignment(assignment: AgentAssignment) → bool

Check whether the assignment is already complete, i.e. all tasks got an agent assigned.

Parameters:

assignment (AgentAssignment) – The current parial assignment.

Returns:

True if the assignment is complete and False otherwise.

Return type:

bool

_heuristic(assignment: AgentAssignment) → float

Computes the heuristic. The heuristic is computed by chosing the best of the remaining agents for each of the remaining tasks and summing the times taken by the chosen agents to perform the remaining tasks.

Parameters:

assignment (AgentAssignment) – The current partial assignhment of agents to tasks.

Returns:

The heuristic estimate.

Return type:

float

examples.agent_assignment.instance module

The classes related to the agent assignment problem and the function for generating the problem instances.

class AATask

Bases: object

A task in the agent assignment problem.

__init__(id: int, agent_costs: List[float])

The constructor

Parameters:

  • id (int) – Task id.

  • agent_costs (List[float]) – For each agent, the time needed to complete the task.

id() → int

Return the task id.

Returns:

The task id.

Return type:

int

__str__() → str

Return the string representation of the task.

Returns:

The string representation of the task.

Return type:

str

class ProblemInstance

Bases: AbstractProblemInstance

An instance of the agent assignment problem.

__init__(id: int, tasks: List[AATask])

The constructor

Parameters:

  • id (int) – Instance id.

  • tasks (List[AATask]) – The list of tasks to which agents need to be optimally assigned.

parameter_titles() → List[str]

Return the tuple of names of the parameters characterizing the instance.

Returns:

The tuple of names of the parameters characterizing the instance.

Return type:

List[str]

parameters() → tuple

Return the tuple of parameters characterizing the instance.

Returns:

The tuple of parameters characterizing the instance.

Return type:

tuple

__str__() → str

Return the string representation of the instance.

Returns:

The string representation of the instance.

Return type:

str

generate_instances(n_tasks: int, n_agents: int, first_id: int, last_id: int) → List[ProblemInstance]

Generate instances of the agent assignment problem. The instance with the same id is guaranteed to be the same between the runs.

Parameters:

  • n_tasks (int) – The number of tasks to which agents will need to be optimally assigned.

  • n_agents (int) – The number of agents.

  • first_id (int) – The id of the first instance.

  • last_id (int) – The id of the first instance.

Returns:

The generated instances.

Return type:

List[ProblemInstance]

examples.agent_assignment.run_client module

This is the user-supplied script to create the Client object and run it. The experiment-specific part of this script is the import of the Task class.

examples.agent_assignment.run_server module

Constructs the Server object and invokes Server.run method.

class Mode

Bases: object

Constant to specify whether the experiment is to be run locally or in GCE.

LOCAL = 'LOCAL'

Run the experiment locally.

GCE = 'GCE'

Run the experiment on GCE.

examples.agent_assignment.task module

class Task

Bases: AbstractTask

__init__(algorithm: Algorithm, timeout=60)

The constructor.

Parameters:

  • algorithm (Algorithm) – The algorithm used to solve the problem instance.

  • timeout (float) – The deadline for the task in seconds.

group_parameter_titles() → Tuple[str]

Return the tuple of names of parameters that determine groups for counting the number of non-hard instances.

Returns:

The tuple of names of parameters that determine groups for counting the number of non-hard instances.

Return type:

Tuple[str]

parameter_titles() → Tuple[str]

Return the tuple of names of parameters that characterize the task.

Returns:

The tuple of names of parameters that characterize the task.

Return type:

Tuple[str]

parameters() → tuple

Return the tuple of parameters that characterize the task.

Returns:

The tuple of parameters that characterize the task.

Return type:

tuple

hardness_parameters() → tuple

Return the tuple of parameters determining the hardness of the task. This is to be used to initialize the Hardness object.

Returns:

The tuple of parameters determining the hardness of the task.

Return type:

tuple

result_titles() → Tuple[str]

Return the tuple of names of output values for the solved task.

Returns:

The tuple of names of output values for the solved task.

Return type:

Tuple[str]

run() → tuple

Return the tuple of output values for the solved task.

Returns:

The tuple of output values for the solved task.

Return type:

tuple