The python implementation is super slow - maybe just a bug?

[Arseni1919]

Hi! I've tried to run the py-lacam code on my device (Macbook Air 1M), but, unfortunatelly, the execution seems to be really slow. Below are the adjsutments that I did. The maps are from the standard benchmark. The algorithm claims to perform really fast, but, maybe, its perfomance is the best only in C++? Can it be the case? I am implementing all of the algorithms in Python, that is why it is really important for me to check this repo. Thank you in advance! The paper is great!

Additional code:

import random

import numpy as np
import re
from typing import TypeAlias
from pycam.mapf_utils import Config

def get_dims_from_pic(img_dir, path='maps'):
    with open(f'{path}/{img_dir}') as f:
        lines = f.readlines()
        height = int(re.search(r'\d+', lines[1]).group())
        width = int(re.search(r'\d+', lines[2]).group())
    return height, width

def get_np_from_dot_map(img_dir, path='maps'):
    with open(f'{path}/{img_dir}') as f:
        lines = f.readlines()
        height, width = get_dims_from_pic(img_dir, path)
        img_np = np.zeros((height, width))
        for height_index, line in enumerate(lines[4:]):
            for width_index, curr_str in enumerate(line):
                if curr_str == '.':
                    img_np[height_index, width_index] = 1
        return img_np, (height, width)

def build_grid(img_dir, path='maps', show_map=False):
    print('Start to build_graph_from_png...')
    img_np, (height, width) = get_np_from_dot_map(img_dir, path)
    return img_np

def get_grid_and_poses(img_dir, num_of_agents, path_to_maps='maps'):
    def fill_the_group(list_of_names, list_of_obj):
        while len(list_of_names) < num_of_agents:
            x_len, y_len = grid.shape
            x, y = random.randint(0, x_len-1), random.randint(0, y_len-1)
            pos_str = f'{x}_{y}'
            if grid[x, y] and pos_str not in list_of_names:
                list_of_names.append(pos_str)
                list_of_obj.append((x, y))

    grid = build_grid(img_dir=img_dir, path=path_to_maps, show_map=False)
    grid = grid > 0
    starts, goals = Config(), Config()
    start_names, goal_names = [], []
    fill_the_group(start_names, starts)
    fill_the_group(goal_names, goals)
    return grid, starts, goals

def main():
    # img_dir='empty-32-32.map'  # 32-32
    img_dir = 'random-32-32-10.map'  # 32-32          | LNS | Up to 400 agents with w=5, h=2, lim=1min.
    # img_dir='random-32-32-20.map'  # 32-32
    # img_dir='room-32-32-4.map'  # 32-32
    # img_dir='maze-32-32-2.map'  # 32-32

    num_of_agents = 10

    grid, starts, goals = get_grid_and_poses(img_dir=img_dir, num_of_agents=num_of_agents)
    print()

if __name__ == '__main__':
    main()

app.py file:

import argparse
from pathlib import Path
from my_grid_and_poses import get_grid_and_poses

from pycam import (
    LaCAM,
    get_grid,
    get_scenario,
    save_configs_for_visualizer,
    validate_mapf_solution,
)

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument(
        "-m",
        "--map-file",
        type=Path,
        default=Path(__file__).parent / "assets" / "tunnel.map",
    )
    parser.add_argument(
        "-i",
        "--scen-file",
        type=Path,
        default=Path(__file__).parent / "assets" / "tunnel.scen",
    )
    parser.add_argument(
        "-N",
        "--num-agents",
        type=int,
        default=2,
    )
    parser.add_argument(
        "-o",
        "--output-file",
        type=str,
        default="output.txt",
    )
    parser.add_argument(
        "-v",
        "--verbose",
        type=int,
        default=1,
    )
    parser.add_argument("-s", "--seed", type=int, default=0)
    parser.add_argument("-t", "--time_limit_ms", type=int, default=100000)
    parser.add_argument(
        "--flg_star", action=argparse.BooleanOptionalAction, default=True
    )

    args = parser.parse_args()

    # my grid and start-goal positions
    # img_dir='empty-32-32.map'  # 32-32
    img_dir = 'random-32-32-10.map'  # 32-32          | LNS | Up to 400 agents with w=5, h=2, lim=1min.
    # img_dir='random-32-32-20.map'  # 32-32
    # img_dir='room-32-32-4.map'  # 32-32
    # img_dir='maze-32-32-2.map'  # 32-32

    num_of_agents = 4
    grid, starts, goals = get_grid_and_poses(img_dir=img_dir, num_of_agents=num_of_agents)

    # solve MAPF
    planner = LaCAM()
    solution = planner.solve(
        grid=grid,
        starts=starts,
        goals=goals,
        seed=args.seed,
        time_limit_ms=args.time_limit_ms,
        flg_star=args.flg_star,
        verbose=args.verbose,
    )
    validate_mapf_solution(grid, starts, goals, solution)

    # save result
    save_configs_for_visualizer(solution, args.output_file)

[Kei18]

Hi! Yes, py-lacam is super slow.

This is because the performance of LaCAM depends on the configuration generator. The papers use PIBT for this, while py-lacam uses random action selection. Note that this repo just serves as a playground.

There is also a PIBT implementation in Python. By combining them, it will be possible to realize a fast version. (Still, c++ is the best for the performance) https://github.com/Kei18/pypibt

[Arseni1919]

Oh.. ok! Is it possible, by any chace, that you could incorporate into LaCAM the required configuration generator (PIBT) in this repo? 🙏 So that we will not make any mistake in doing so. In our case, the algorithms, that are written in the same language are good for inter-comparison (despite the fact, that C++ is know to be much faster). Thank you a lot for a quick response!

[Kei18]

I see. The Python implementation is possible and not a hard task. I think it only has to add about 100 lines. But I do not have the bandwidth at the moment. I cannot promise when I will do it...

[Arseni1919]

Oh.. it is tottaly fine! At your earliest convenience, and thank you a lot in advance! Thank you for your response!

[Kei18]

Okay, I will notify you when it is done.

Cheers, Keisuke

[Kei18]

@Arseni1919 I eventually wrote a code for LaCAM-PIBT. https://github.com/Kei18/py-lacam/tree/pibt

Please note that I did not go into code-level optimization or performance optimization of the algorithm itself. It's at the proof-of-concept level.

[Arseni1919]

Thank you! It really helps us a lot!:) I will try to run it shortly. Thanks 🙏