Combinatorial Search with Generators

Keisuke Okumura | 奥村圭祐

June 20, 2025

Tweet Share

Transcript

1. Combinatorial Search with Generators kei18 https://kei18.github.io[email protected] 16th May. 2024,

   Monash University Keisuke Okumura1,2 1University of Cambridge 2National Institute of Advanced Industrial Science and Technology (AIST) Image by Oberholster from Pixabay

2. /59 2 0, 1, 1, 2, 3, 5, 8, 13,

   21, …

3. /59 3 F0 F1 Fn = 0 = 1 =

   Fn-1 + Fn-2 Fibonacchi Sequence Image by Karin Henseler from Pixabay

4. /59 4 Python Coding - Recursive

5. /59 5 Python Coding - Iterative

6. /59 6 Python Coding - Generative Pause the process. You

   can resume from here the next time you call.

7. /59 7 When are Generators Useful? tokenization

8. /59 8 Data Stream Data Batch Generator Computation Image by

   Oberholster and Venita Prawny from Pixabay

9. /59 9 Data Batch Generator Data Stream Computation

10. /59 10 start goal Combinatorial Search start goal f =

    g + h search tree

11. /59 11 Combinatorial Search start goal search tree branching factor

    (number of successor nodes) grid pathfinding 25-40 chess 4 e.g.,

12. /59 12 difficult / impossible to list all e.g., ≥

    #atoms in the universe Sometimes We Encounter:

13. /59 13 Data Stream

14. /59 14 Successor Batch Combinatorial Search with Generators

15. /59 15 Pathfinding with Massive Implicit Edges

16. /59 16 start goal 10,000 vertices connected to another if

    they can see each other i.e., |E| = O(|V|2) obstacle

17. /59 17

18. /59 18 with Julia Implementation A*: failed with 1h timeout

    Greedy Best-First Search: ≥9min RRT-Connect: ≥3min (ignoring vertices)

19. /59 19 Limiting Successors – Nearest Neighbors start goal 3

    neighbors excluded from search effort

20. /59 20 Limiting Successors - Pitfall start goal obstacle 3

    neighbors

21. /59 21 perfect but inefficient efficient but imperfect

22. /59 22 Generator: K-Nearest Neighbor Search on K-d Tree

23. /59 23 K-d Tree data structure suitable to query for

    the nearest points

24. /59 24 data structure suitable to query for the nearest

    points K-d Tree

25. /59 25 data structure suitable to query for the nearest

    points K-d Tree

26. /59 26 data structure suitable to query for the nearest

    points omitting backtracking phase finding the nearest neighbor : brute force k-d tree O(n) O(log n) easy to extend: “find k nearest neighbors with distance >θ” K-d Tree

27. /59 27 K-d Tree Search as Generator Setup: Set distance

    threshold θ as zero For each call: 1. Find k nearest neighbors with distance >θ 2. Update θ to a max distance within the batch

28. /59 28 Pathfinding with Generator 1st visit

29. /59 29 Pathfinding with Generator 2nd visit

30. /59 30 Pathfinding with Generator excluded from search effort

31. /59 31 If We Continue 1st visit

32. /59 32 If We Continue 2nd visit

33. /59 33 If We Continue

34. /59 34 Anytime Algorithm previous updated that eventually converges to

    optimal solutions

35. /59 35 Setup: Set distance threshold θ as zero For

    each call: 1. Find k nearest neighbors with distance >θ 2. Update θ to a max distance within the batch K-d Tree Generator adding constraints lazily to visit all successors eventually Lazy Constraints Addition Search for single-agent; LaCAS(*)

36. /59 36 Demo of LaCAS solution path search progress start

    goal

37. /59 37 with Julia Implementation A*: failed with 1h timeout

    Greedy Best-First Search: ≥9min RRT-Connect: ≥3min (ignoring vertices) LaCAS: ~30s LaCAT: ~40s (Theta* like LaCAS) LaCAT* after 10 min (anytime algorithm)

38. /59 38 Starting from unbounded suboptimal solutions Easy to design

    anytime algorithm that eventually converges to optimal solutions => Useful for problems with huge branching factors Gradually generate successors as the search progress Characteristics of Combinatorial Search with Generators

39. /59 39 => MAPF: Multi-Agent Pathfinding Pathfinding with massive implicit

    edges; Understood, but too simple. More convincing examples?

40. /59 40 given agents graph goals solution paths without collisions

    cost total travel time, distance, makespan, etc MAPF: Multi-Agent Path Finding

41. /59 41 AP Photo/Ross D. Franklin Ross D. Franklin /

    AP Photo "Swarm" automation is ubiquitous

42. /59 42 … … … … … search node (configuration)

    goal configuration Vanilla A* for MAPF

43. /59 43 runtime (sec) solved instances (%)   

                - 13,900 instances - 33 grid maps - every 50 agents, up to max. (1000) - tested on standard desktop PC Stern, R. et al. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks. SoCS. 2019. 33 grid maps e.g., random-32-32-20, 200 agents Evaluation on MAPF benchmark maze-32-32-2, 100 agents 00.0% A* [Hart+ 68] complete optimal algorithm properties computation time

44. /59 44 Reason for Poor Performance of A* O(5^N) N:

    #agents MAPF has a huge branching factor: 3,125 9,765,625 95,367,431,640,625 931,322,574,615,478,515,625 9,094,947,017,729,282,379,150,390,625 88,817,841,970,012,523,233,890,533,447,265,625 5^5 5^10 5^20 5^30 5^40 5^50 For 10k agents? Ridiculous!

45. /59 45 Data Stream Generator: MAPF Algorithm with Short Planning

    Horizon

46. /59 must go left in the next config. 46 constraint

    tree (maintained implicitly) configuration (search node) Generator for MAPF – 1/4

47. /59 47 1st invoke configuration generation with no constraint Generator

    for MAPF – 1/4

48. /59 48 2nd invoke configuration generation with Generator for MAPF

    – 1/4

49. /59 49 e.g., breadth-first search 24th invoke configuration generation with

    eventually visit all neighbor configurations Generator for MAPF – 1/4

50. /59 50 How can we generate a promising configuration following

    constraints?

51. /59 51 PIBT PIBT initial configuration PIBT goal configuration There

    are MAPF algorithms that sequentially generate configurations, e.g., PIBT Okumura, K., Machida, M., Défago, X., & Tamura, Y. Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding. AIJ. 2022. (extended from IJCAI’19*) use such algorithms to generate promising configurations

52. /59 52 For each call: 1. Develop the constraint tree

    2. Generate configurations with constraints using short-horizon MAPF algorithms Generator for MAPF adding constraints lazily to visit all successors eventually Lazy Constraints Addition Search for multi-agent; LaCAM(*)

53. /59 53 A* / PIBT 0% with 400 agents 100%,

    worst: 11sec LaCAM #agents success rate random-32-32-20, 32x32, 30sec timeout, 400 agents Performance of LaCAM           

54. /59 54        

           67.4% PIBT 0.0% A* [Hart+ 68] 99.0% LaCAM*+ fine-tuned PIBT runtime (sec) solved instances (%) Okumura, K. Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding. IJCAI. 2023. 85.6% LaCAM + vanilla PIBT Okumura, K. LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding. AAAI. 2023. Okumura, K., Machida, M., Défago, X., & Tamura, Y. Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding. AIJ. 2022.

55. /59 55        

           runtime (sec) solved instances (%) 0.0% A* [Hart+ 68] 0.4% ODrM* [Wagner+ AIJ’15] 8.3% CBS [Sharon+ AIJ’15; Li+ AIJ’21] 10.7% BCP [Lam+ COR’22] 30.9% I-ODrM*-5 [Wagner+ AIJ’15] 50.5% EECBS-5 [Li+ AAAI’21] 61.4% PP [Silver AIIDE’05] 80.9% LNS2 [Li+ AAAI’22] 67.4% PIBT [Okumura+ AIJ’22] complete solution complete complete solution complete bounded suboptimal bounded suboptimal optimal optimal (unable to identify unsolvable instances) incomplete suboptimal 85.6% LaCAM [Okumura AAAI’23] 99.0% LaCAM* [Okumura IJCAI’23] complete complete eventually optimal suboptimal lose nice props.

56. /59 56 LaCAM* suboptimally solves MAPF for 10k agents in

    a warehouse-style map with many narrow corridors, in 5 seconds on my laptop

57. /59 59 Summary: Combinatorial Search with Generators Successor Batch Generator

    Search Pathfinding with Massive Implicit Edges Multi-Agent Pathfinding

58. /59 60 Thank you for listening! Acknowledgements to mentors /

    collaborators: X. Defago, Y. Tamura, F. Bonnet + members of DEFAGO Lab (TokyoTech) R. Yonetani + co-authors (OSX) S. Tixeuil (LIP6, Sorbonne) J. Alkazzi (idealworks) A. Prorok + members of PROROK Lab (Cambridge) Funding: JSPS DC & Overseas Research Fellowship, JST ACT-X, Yoshida Scholarship Foundation kei18 https://kei18.github.io[email protected] Questions / research collaboration proposals are welcome: