Skip to content

BinPack

BinPack (Environment) #

Problem of 3D bin packing, where a set of items have to be placed in a 3D container with the goal of maximizing its volume utilization. This environment only supports 1 bin, meaning it is equivalent to the 3D-knapsack problem. We use the Empty Maximal Space (EMS) formulation of this problem. An EMS is a 3D-rectangular space that lives inside the container and has the following

Properties

  • It does not intersect any items, and it is not fully included into any other EMSs.
  • It is defined by 2 3D-points, hence 6 coordinates (x1, x2, y1, y2, z1, z2), the first point corresponding to its bottom-left location while the second defining its top-right corner.

  • observation: Observation

    • ems: EMS tree of jax arrays (float if normalize_dimensions else int32) each of shape (obs_num_ems,), coordinates of all EMSs at the current timestep.
    • ems_mask: jax array (bool) of shape (obs_num_ems,) indicates the EMSs that are valid.
    • items: Item tree of jax arrays (float if normalize_dimensions else int32) each of shape (max_num_items,), characteristics of all items for this instance.
    • items_mask: jax array (bool) of shape (max_num_items,) indicates the items that are valid.
    • items_placed: jax array (bool) of shape (max_num_items,) indicates the items that have been placed so far.
    • action_mask: jax array (bool) of shape (obs_num_ems, max_num_items) mask of the joint action space: True if the action (ems_id, item_id) is valid.

  • action: MultiDiscreteArray (int32) of shape (obs_num_ems, max_num_items).

    • ems_id: int between 0 and obs_num_ems - 1 (included).
    • item_id: int between 0 and max_num_items - 1 (included).

  • reward: jax array (float) of shape (), could be either:

    • dense: increase in volume utilization of the container due to packing the chosen item.
    • sparse: volume utilization of the container at the end of the episode.

  • episode termination:

    • if no action can be performed, i.e. no items fit in any EMSs, or all items have been packed.
    • if an invalid action is taken, i.e. an item that does not fit in an EMS or one that is already packed.

  • state: State

    • coordinates: jax array (float) of shape (num_nodes + 1, 2) the coordinates of each node and the depot.
    • demands: jax array (int32) of shape (num_nodes + 1,) the associated cost of each node and the depot (0.0 for the depot).
    • position: jax array (int32) the index of the last visited node.
    • capacity: jax array (int32) the current capacity of the vehicle.
    • visited_mask: jax array (bool) of shape (num_nodes + 1,) binary mask (False/True <--> not visited/visited).
    • trajectory: jax array (int32) of shape (2 * num_nodes,) identifiers of the nodes that have been visited (set to DEPOT_IDX if not filled yet).
    • num_visits: int32 number of actions that have been taken (i.e., unique visits).
1
2
3
4
5
6
7
8
from jumanji.environments import BinPack
env = BinPack()
key = jax.random.PRNGKey(0)
state, timestep = jax.jit(env.reset)(key)
env.render(state)
action = env.action_spec.generate_value()
state, timestep = jax.jit(env.step)(state, action)
env.render(state)

observation_spec: jumanji.specs.Spec[jumanji.environments.packing.bin_pack.types.Observation] cached property writable #

Specifications of the observation of the BinPack environment.

Returns:

Type Description
Spec for the `Observation` whose fields are
  • ems:
    • if normalize_dimensions: tree of BoundedArray (float) of shape (obs_num_ems,).
    • else: tree of BoundedArray (int32) of shape (obs_num_ems,).
  • ems_mask: BoundedArray (bool) of shape (obs_num_ems,).
  • items:
    • if normalize_dimensions: tree of BoundedArray (float) of shape (max_num_items,).
    • else: tree of BoundedArray (int32) of shape (max_num_items,).
  • items_mask: BoundedArray (bool) of shape (max_num_items,).
  • items_placed: BoundedArray (bool) of shape (max_num_items,).
  • action_mask: BoundedArray (bool) of shape (obs_num_ems, max_num_items).

action_spec: MultiDiscreteArray cached property writable #

Specifications of the action expected by the BinPack environment.

Returns:

Type Description
MultiDiscreteArray (int32) of shape (obs_num_ems, max_num_items). - ems_id

int between 0 and obs_num_ems - 1 (included). - item_id: int between 0 and max_num_items - 1 (included).

__init__(self, generator: Optional[jumanji.environments.packing.bin_pack.generator.Generator] = None, obs_num_ems: int = 40, reward_fn: Optional[jumanji.environments.packing.bin_pack.reward.RewardFn] = None, normalize_dimensions: bool = True, debug: bool = False, viewer: Optional[jumanji.viewer.Viewer[jumanji.environments.packing.bin_pack.types.State]] = None) special #

Instantiates a BinPack environment.

Parameters:

Name Type Description Default
generator Optional[jumanji.environments.packing.bin_pack.generator.Generator]

Generator whose __call__ instantiates an environment instance. Implemented options are [RandomGenerator, ToyGenerator, CSVGenerator]. Defaults to RandomGenerator that generates up to 20 items maximum and that can handle 40 EMSs.

 None
obs_num_ems int

number of EMSs (possible spaces in which to place an item) to show to the agent. If obs_num_ems is smaller than generator.max_num_ems, the first obs_num_ems largest EMSs (in terms of volume) will be returned in the observation. The good number heavily depends on the number of items (given by the instance generator). Default to 40 EMSs observable.

 40
reward_fn Optional[jumanji.environments.packing.bin_pack.reward.RewardFn]

compute the reward based on the current state, the chosen action, the next state, whether the transition is valid and if it is terminal. Implemented options are [DenseReward, SparseReward]. In each case, the total return at the end of an episode is the volume utilization of the container. Defaults to DenseReward.

 None
normalize_dimensions bool

if True, the observation is normalized (float) along each dimension into a unit cubic container. If False, the observation is returned in millimeters, i.e. integers (for both items and EMSs). Default to True.

 True
debug bool

if True, will add to timestep.extras an invalid_ems_from_env field that checks if an invalid EMS was created by the environment, which should not happen. Computing this metric slows down the environment. Default to False.

 False
viewer Optional[jumanji.viewer.Viewer[jumanji.environments.packing.bin_pack.types.State]]

Viewer used for rendering. Defaults to BinPackViewer with "human" render mode.

 None

reset(self, key: PRNGKeyArray) -> Tuple[jumanji.environments.packing.bin_pack.types.State, jumanji.types.TimeStep[jumanji.environments.packing.bin_pack.types.Observation]] #

Resets the environment by calling the instance generator for a new instance.

Parameters:

Name Type Description Default
key PRNGKeyArray

random key used to reset the environment.

 required

Returns:

Type Description
state

State object corresponding to the new state of the environment after a reset. timestep: TimeStep object corresponding the first timestep returned by the environment after a reset. Also contains the following metrics in the extras field: - volume_utilization: utilization (in [0, 1]) of the container. - packed_items: number of items that are packed in the container. - ratio_packed_items: ratio (in [0, 1]) of items that are packed in the container. - active_ems: number of active EMSs in the current instance. - invalid_action: True if the action that was just taken was invalid. - invalid_ems_from_env (optional): True if the environment produced an EMS that was invalid. Only available in debug mode.

step(self, state: State, action: Union[jax.Array, numpy.ndarray, numpy.bool_, numpy.number]) -> Tuple[jumanji.environments.packing.bin_pack.types.State, jumanji.types.TimeStep[jumanji.environments.packing.bin_pack.types.Observation]] #

Run one timestep of the environment's dynamics. If the action is invalid, the state is not updated, i.e. the action is not taken, and the episode terminates.

Parameters:

Name Type Description Default
state State

State object containing the data of the current instance.

 required
action Union[jax.Array, numpy.ndarray, numpy.bool_, numpy.number]

jax array (int32) of shape (2,): (ems_id, item_id). This means placing the given item at the location of the given EMS. If the action is not valid, the flag invalid_action will be set to True in timestep.extras and the episode terminates.

 required

Returns:

Type Description
state

State object corresponding to the next state of the environment. timestep: TimeStep object corresponding to the timestep returned by the environment. Also contains metrics in the extras field: - volume_utilization: utilization (in [0, 1]) of the container. - packed_items: number of items that are packed in the container. - ratio_packed_items: ratio (in [0, 1]) of items that are packed in the container. - active_ems: number of EMSs in the current instance. - invalid_action: True if the action that was just taken was invalid. - invalid_ems_from_env (optional): True if the environment produced an EMS that was invalid. Only available in debug mode.

render(self, state: State) -> Optional[numpy.ndarray[Any, numpy.dtype[+ScalarType]]] #

Render the given state of the environment.

Parameters:

Name Type Description Default
state State

State object containing the current dynamics of the environment.

 required

close(self) -> None #

Perform any necessary cleanup.

Environments will automatically :meth:close() themselves when garbage collected or when the program exits.

Last update: 2024-03-29
Back to top