Crate caboose

CaBooSe (Conflict-Based Search) is a crate implementing the Continuous Conflict-Based Search algorithm (CCBS) for the Multi-Agent Path Finding problem (MAPF). It uses the Safe Interval Path Planning algorithm (SIPP) algorithm under the hood to plan individual paths while avoiding already processed collisions. Furthermore, SIPP itself uses the Reverse Resumable A* algorithm (RRA*) to compute heuristics for each task to solve.

Usage

The main entry point of the crate is the ConflictBasedSearch struct, which requires a TransitionSystem to be created. It can then be used to plan paths for a set of agents, by calling the ConflictBasedSearch::solve function on a CbsConfig that gathers all the information needed to solve the problem.

Example

use ordered_float::OrderedFloat;
use std::sync::Arc;
use caboose::{
   simple_graph, SimpleWorld, SimpleState, SimpleHeuristic, GraphNodeId, GraphEdgeId,
   ConflictBasedSearch, CbsConfig, Task,
};

let size = 10;
let graph = simple_graph(size);
let transition_system = Arc::new(SimpleWorld::new(graph, 0.4));
let tasks = vec![
    Arc::new(Task::new(
        SimpleState(GraphNodeId(0)),
        SimpleState(GraphNodeId(9)),
        OrderedFloat(0.0),
    )),
    Arc::new(Task::new(
        SimpleState(GraphNodeId(9)),
        SimpleState(GraphNodeId(0)),
        OrderedFloat(0.0),
    )),
];
let config: CbsConfig<
    SimpleWorld,
    SimpleState,
    GraphEdgeId,
    OrderedFloat<f64>,
    OrderedFloat<f64>,
    SimpleHeuristic,
> = CbsConfig::new(
    transition_system.clone(),
    tasks,
    OrderedFloat(1e-6),
    1,
    None,
);
let mut solver = ConflictBasedSearch::new(transition_system.clone());
let solutions = solver.solve(&config).unwrap();

Lifelong

A second entry point of the crate is the Lifelong struct, which can process a stream of planning requests. Each of those requests can ask for new paths for a subset of agents, and those must avoid collisions with the last planned paths for the other agents.

Genericity

Caboose allows to specify new environments by implementing the TransitionSystem trait. It reasons over:

• a set of states, implementing the State trait, that describe the state of an agent;
• a set of actions that describe the possible moves of an agent, depending on its state;

and requires implementing a few functions that link them together, in particular:

• TransitionSystem::actions_from and TransitionSystem::transition to describe the result of applying an action to a state;
• TransitionSystem::transition_cost to describe the cost of applying an action to a state (i.e. the duration of the action);
• TransitionSystem::conflict that checks whether two actions performed by two different agents lead to a collision.

You will probably also need to create a simple heuristic for your environment by implementing the Heuristic trait. This heuristic will be used by the search algorithm to guide the search, but should be simplistic as it will only be used to guide the search for a more advanced heuristic given by ReverseResumableAStar.

Structs

• Action
  Wrapper around an action that also contains the cost of the action.
• CbsConfig
  Input configuration for the Conflict-Based Search algorithm.
• CbsStats
  Statistics of the Conflict-Based Search algorithm.
• Config
  An algorithm configuration to use to solve benchmark instances.
• ConflictBasedSearch
  Implementation of the Conflict-Based Search algorithm that plans collision-free paths for a set of agents.
• DifferentialHeuristic
  Differential heuristic built on top of heuristics dealing with time and durations.
• GeneralizedSippConfig
  Input configuration for the Generalized Safe Interval Path Planning algorithm.
• Graph
  Definition a weighted directed graph.
• GraphEdge
  Definition of a directed graph edge.
• GraphEdgeId
  A directed graph edge id.
• GraphNode
  Definition of a directed graph node.
• GraphNodeId
  A directed graph node id.
• Interval
  Defines a time interval (start <= end).
• LSippConfig
  Input configuration for the Safe Interval Path Planning algorithm with landmarks.
• LSippStats
  Statistics of the Safe Interval Path Planning algorithm with landmarks.
• Lifelong
  A lifelong planner that supports requests for new tasks while other tasks are being executed. It uses Conflict-Based Search under the hood.
• LifelongConfig
  The input configuration for a new planning request.
• Move
  Definition of a move in a transition system.
• ReverseResumableAStar
  Implementation of the Reverse Resumable A* algorithm that computes the shortest path between:
• RraStats
  Statistics of the Reverse Resumable A* algorithm.
• SafeIntervalPathPlanning
  Implementation of the Safe Interval Path Planning algorithm that computes the optimal sequence of actions to complete a given task in a given transition system, while avoiding conflicts with other agents in the same environment.
• SafeIntervalPathPlanningWithLandmarks
  Implementation of Safe Interval Path Planning algorithm that supports landmarks (or positive constraints) to visit before aiming for the goal state.
• SimpleHeuristic
  A heuristic that returns the time to connect two vertices of the graph in straight line.
• SimpleState
  A state in the simple world, simply represented by a GraphNodeId.
• SimpleWorld
  A world simply described by a directed weighted graph
• SippConfig
  Input configuration for the Safe Interval Path Planning algorithm.
• SippState
  State wrapper for the Safe Interval Path Planning algorithm that extends a given state definition with a safe interval.
• SippStats
  Statistics of the Safe Interval Path Planning algorithm.
• SippTask
  Task wrapper for the Safe Interval Path Planning algorithm that extends a given task definition with all SIPP states that correspong to it.
• Solution
  Description of a solution to a search problem
• Task
  Definition of a task in a given transition system that can then be fed to a search algorithm.

Traits

• ActionCallback
  Definition of a callback that can be used to apply actions to a transition system.
• Heuristic
  Defines a heuristic function that can be used by a search algorithm, for a given transition system and task.
• HeuristicBuilder
  Trait to build heuristics on the fly.
• LimitValues
  Trait to specify the minimum and maximum values of a type.
• State
  Definition of a state in a transition system.
• TransitionSystem
  Definition of a transition system that contains a set of states and actions, and transition functions that describe the result of any action applied to any state. The reverse transitions must also be described to allow using the reverse search as a heuristic.

Functions

• get_cbs_from_files
  Builds a CBS algorithm and its configuration from the given files.
• parse_config
  Parse a configuration file.
• parse_inputs
  Parse the benchmark maps and scenarios from https://movingai.com/benchmarks/mapf/index.html
• read_from_file
  Parse the benchmark maps and scenarios from https://movingai.com/benchmarks/mapf/index.html
• simple_graph

Type Aliases

• MyTime
  A wrapper around f64 that implements Ord and LimitValues.
• SimpleEdgeData
  The distance between two nodes in the graph.
• SimpleNodeData
  The (x,y) coordinates of a node in the graph.