Crate caboose

Expand description

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.

Crate cabooseCopy item path