pathplanning / continuous-cbs

Continuous CBS - a modification of conflict based search algorithm, that allows to perform actions (move, wait) of arbitrary duration. Timeline is not discretized, i.e. is continuous.

Continuous-CBS

Continuous CBS (CCBS) is a modification of the Conflict Based Search (CBS) algorithm, that supports actions (both move or wait) of arbitrary duration. CCBS is different from CBS in the way how conflicts and constraints are defined. To handle CCBS constraints the low-level search is inspired by Safe Interval Path Planning (SIPP) algorithm. More info about CCBS can be found at IJCAI19 paper.

The master-version supports both grids and general graphs (roadmaps) as well as it supports the following enhancements:

• Disjoint Splitting (DS)
• Prioritizing conflicts (PC)
• High-level heuristics (H)

The detailed description of these enhancements can be found at AAAI21 paper.

Content

Content that compliments the source code of CCBS is organized into the following folders:

• Demos - contains animations of the solutions obtained by CCBS.
• Examples - contains the examples of input/output XML-files required/provided by the algorithm.
• Instances - contains the archives with the maps and instances (in the format that CCBS supports), that were used for the experimental evaluation described in the abovementioned papers on CCBS.
• ExpResults - contains the raw tabular results obtained during the experimental evaluation of CCBS algorithm.
• Releases - not a folder, but the tagged commits that were used to get the results for the corresponding papers.

Getting Started

To go and try this algorithm you can use QtCreator or CMake. Both .pro and CMakeLists files are available in the repository.

Notice, that project uses C++11 standart. Make sure that your compiler supports it.

These instructions will get you a copy of the project up and running on your local machine for development and testing purposes.

Prerequisites

Qt Creator — a cross-platform C++, JavaScript and QML integrated development environment which is part of the SDK for the Qt GUI Application development framework.

CMake — an open-source, cross-platform family of tools designed to build, test and package software.

Installing

Download current repository to your local machine. Use

git clone https://github.com/PathPlanning/Continuous-CBS.git

or direct downloading.

Built current project using Qt Creator or CMake. To launch the compiled file you will need to pass input XML file as an argument. Output file for this project will be placed in the same folder as input file and, by default, will be named _log.xml. For examlpe, using CMake

cd PATH_TO_THE_PROJECT
cmake .
make

Input and Output files

The examples of input and output files you can find in the Examples folder.

Options

There are some options that can be controlled either through the const.h file or through the input configuration file (see examples):

• <use_cardinal> - controls whether the algorithm is looking for cardinal and semi-cardinal collisions or not. Possible values are 1(true) or 0 (false).
• <use_disjoint_splitting> - controls whether the algotihm uses disjoint splitting enhancement or not. Possible values are 1(true) or 0 (false).
• <hlh_type> - controls whether the algorithm uses high-level heuristics or not. 2 different heursitics are implemented. 0 - HL-heuristic is disabled; 1 - HL-heuristic based on solving linear programming problem (by simplex method); 2 - HL-heurstic based an greedy selection of disjoint cardinal conflicts.
• <connectedness> - controls the connectedness of the grid. Possible values: 2 - 4 cardinal neighbors; 3 - 4 cardinal + 4 diagonal; 4 - 16 neighbors; 5 - 32 neighbors. In case if the map is represented as roadmap this parameter is ignored.
• <timelimit> - controls the maximum runtime of the algorithm. Possible values are >0. For example value 60 means that the algorithm can spend up to 60 seconds to find a solution.
• <agent_size> - controls the size (radii) of the agents' shape. Possible values are in the range (0, 0.5].
• <precision> - additional option, that controls how precise the end of collision interval is detected (the moment of time when there is no more collision between the agents). The lower the value - the preciser the algorithm finds the end of collision interval, but it takes a bit more time. Possible values are >0.

If some of these tags are not defined in the input configuraton file or there is no config-file, all the values of the absent parameters are taken from the 'const.h' file.

Launch

To launch the application you need to have at least map and task input XML-files with all required information:

./CCBS map.xml task.xml

If you want to control the parameters through the input config file, you need to launch the application with three parameters:

./CCBS map.xml task.xml config.xml

The output file will be placed in the same folder as input files and, by default, will be named as task-file plus _log.xml. For examlpe,

"initial_task_file_name.xml" -> "initial_task_file_name_log.xml"

continuous-cbs's Issues

visual

I have a question ,How to realize the visualization of resultion like "Demos" floder?

the value of CN_AGENT_SIZE

Why is the value of CN_AGENT_SIZE only supported between 0 and 0.5

Which tool can be used to show the search result like animations in DEMO？

Which tool can be used to show the search result like animations in DEMO？

roadmap visualization

Dear @aandreychuk,

gridmap types is possibly visualized by using the tool provided in this #7 . However, roadmap type does not seem to follow that template.

I'm struggling on simulating the results from roadmap. Any suggestion on this issue.

Thanks so much for the work.

Setting CN_AGENT_SIZE > 0.5 causes segfault

Using the following map/task: Examples.zip setting CN_AGENT_SIZE > 0.5 causes a segmentation fault with all other settings at default. Some debugging shows this starts with Map::check_line - within Map::get_grid.

Is CN_AGENT_SIZE > 0.5 meant to be supported?

puzzled in merging wait constrains operation

excuse me , i am reading your outstanding work.
i want to confirm if the following process exists mistake.
i think that only if one interval overlaps with the following one i.e.[i].second > [i+1].first, a merge operation can be performed.

    for(unsigned int i = 0; i + 1 < collision_intervals[id].size(); i++)
        if(collision_intervals[id][i].second - CN_EPSILON < collision_intervals[id][i+1].first)
        {
            collision_intervals[id][i].second = collision_intervals[id][i+1].second;
            collision_intervals[id].erase(collision_intervals[id].begin() + i + 1);
            i--;
        }

function check_conflict may exist error

Parameters m1i1 m1i2 ...in function check_conflict shall be changed to double?