Summary of Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders For More Efficient Multi-agent Path Finding Plan Execution, by Yifan Su et al.
Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution
by Yifan Su, Rishi Veerapaneni, Jiaoyang Li
First submitted to arxiv on: 30 Dec 2023
Categories
- Main: Artificial Intelligence (cs.AI)
- Secondary: Multiagent Systems (cs.MA); Robotics (cs.RO)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary The Multi-Agent Path Finding problem involves planning paths for multiple agents in a shared environment without collisions. Most current solutions rely on the assumption that each agent can arrive at a specific location at a specific time. However, real-world uncertainties can cause agents to deviate from this assumption, leading to collisions and deadlocks. To address this issue, we introduce a new representation called Bidirectional Temporal Plan Graph (BTPG) that allows adjusting passing orders during execution to reduce unnecessary waiting times. We design two anytime algorithms for constructing BTPGs: BTPG-naïve and BTPG-optimized. Experimental results show that using BTPGs outperforms traditional approaches, reducing waiting times by 8-20%. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The Multi-Agent Path Finding problem is about helping multiple robots or agents move around a shared space without crashing into each other. Usually, these agents follow a plan to make sure they don’t collide, but real-world situations can cause them to deviate from this plan, leading to problems. To fix this, we came up with a new way of planning called Bidirectional Temporal Plan Graph (BTPG) that lets agents adjust their path during execution to avoid waiting unnecessarily. We tested two ways to create BTPGs and found that they work better than the traditional approach, saving time by 8-20%. |
