Continuous Conflict-Based Search (CCBS) implementation in Python

Ported from C++ implementation, available at https://github.com/PathPlanning/Continuous-CBS

Python port resembles the file structure of the original repository.

• ccbs.py: implementation of the CCBS algorithm
• config.py: configuration of the CCBS
• map.py: object for dealing with maps
• sipp.py: implementation of SIPP algorithm
• structs.py: helping object structures for SIPP and CCBS
• test map map_ccbs.export.xml, task list task_ccbs_export.xml

Both SIPP and CCBS can be used directly. SIPP can be used separately.

Map loading code uses libraries networkx and matplotlib.

The following example loads the map from .xml, adds some example constraints (both positive and negative), then plans the path for one agent

    map = Map("map_ccbs_export.xml")

    planner = SIPP(map)
    planner.verbose = True # Opional

    # Add constraints
    cs = []
    cs.append(Constraint(0, 250, 260, 240, 547, True)) # Must traverse 240-547 at t = 250-260
    cs.append(Constraint(1, 40, 160, 240, 240, False)) # Collision constraint by agent 1 on node 240 at t = 40-160

    planner.find_path(Agent(35, 85, 0), cs) # Plan path between nodes 35 and 85 for agent 0

CCBS is a multi-agent optimal planner

    map = Map("map_ccbs_export.xml")

    ccbs = CCBS(map)

    # Create task
    task = Task()

    # Load tasks
    task.agents.append(Agent(35, 85, 0))
    task.agents.append(Agent(161, 113, 1))
    task.agents.append(Agent(105, 19, 2))
    task.agents.append(Agent(73, 69, 3))
    task.agents.append(Agent(201, 179, 4))
    
    # Run CCBS
    solution = ccbs.find_solution(task)    

    # Render the map graphically
    map.render(solution.paths)

    # Save solution to file
    ccbs.write_to_log_path('test_out.xml')

Tasks can also be loaded from file directly

    task.load_from_file("task_ccbs_export.xml") 

• x,y based map
• no simplex-based optimization supported for HL-heuristic
• additional distance trigger for conflicts checking in function check_paths in ccbs.py (check for nodes distance at end of motion interval)