PaperlayerView exact revision on arXiv

Source-linked AI summary

Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery

Hang Ma, Wolfgang Hönig, T. K. Satish Kumar, Nora Ayanian, Sven Koenig

arXiv:1812.06355v1cs.AIcs.RO

TL;DR

MAPD requires agents to complete a stream of pickup-and-delivery tasks without collisions. The paper uses SIPPwRT within Token Passing to plan continuous, velocity-aware robot movements directly. TP-SIPPwRT guarantees safety distance and solves well-formed MAPD instances.

  • Problem

    MAPD algorithms such as Token Passing use discrete grid movements at uniform velocity, while adapting those plans afterward to continuous movements may yield ineffective paths.

    Source: Introduction · p. 1

  • Method

    The paper replaces Token Passing’s single-agent planner with SIPPwRT, using a reservation table to efficiently calculate safe intervals and update or delete path reservations.

    Source: Reservation Table and Safe Intervals · pp. 2–3

  • Results

    TP-SIPPwRT guarantees a safety distance between agents and solves all well-formed MAPD instances.

    Source: Introduction · p. 1, Pseudocode · p. 5

  • Takeaways & Limitations

    TP-SIPPwRT plans continuous forward movements and point turns at given velocities directly, rather than adapting discrete paths afterward.

    Source: Introduction · p. 1

    The stated robot model assumes disk-shaped agents, instantaneous acceleration and deceleration, and movement between adjacent cell centers; completeness is stated for well-formed MAPD instances.

    Source: TP-SIPPwRT · p. 2

Abstract

from arXiv · show

The Multi-Agent Pickup and Delivery (MAPD) problem models applications where a large number of agents attend to a stream of incoming pickup-and-delivery tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and effective. We make TP even more efficient and effective by using a novel combinatorial search algorithm, called Safe Interval Path Planning with Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an advanced data structure that allows for fast updates and lookups of the current paths of all agents in an online setting. The resulting MAPD algorithm TP-SIPPwRT takes kinematic constraints of real robots into account directly during planning, computes continuous agent movements with given velocities that work on non-holonomic robots rather than discrete agent movements with uniform velocity, and is complete for well-formed MAPD instances. We demonstrate its benefits for automated warehouses using both an agent simulator and a standard robot simulator. For example, we demonstrate that it can compute paths for hundreds of agents and thousands of tasks in seconds and is more efficient and effective than existing MAPD algorithms that use a post-processing step to adapt their paths to continuous agent movements with given velocities.

Introduction

MAPD assigns agents a stream of pickup-and-delivery tasks in a grid while requiring collision avoidance. This paper extends Token Passing with continuous, velocity-aware path planning rather than relying on post-processing to adapt discrete plans.

Introduction

  • MAPD models agents completing incoming pickup-and-delivery tasks by traveling from each task’s pickup cell to its delivery cell while avoiding collisions.An instance is solved when all tasks are completed within a bounded time after insertion.Source: Introduction · p. 1
  • The multi-agent pathfinding problem, used in most MAPD algorithms’ inner loops, is NP-hard to solve optimally.Approaches include reductions to other combinatorial problems and dedicated search algorithms.Source: Introduction · p. 1
  • Token Passing (TP) plans time-minimal collision-free paths but assumes discrete grid movements at uniform velocity, so post-processing may produce ineffective paths.MAPF-POST adapts paths to continuous forward movements and point turns, but TP planning is oblivious to that transformation.Source: Introduction · p. 1
  • TP-SIPPwRT replaces TP’s path planner with SIPPwRT to plan continuous movements and turns at given velocities, guaranteeing inter-agent safety distance and completeness for well-formed MAPD instances.SIPPwRT improves SIPP for this and other applications.Source: Introduction · p. 1

TP-SIPPwRT

TP repeatedly plans paths for agents while treating other agents’ committed paths as dynamic obstacles. TP-SIPPwRT replaces discrete space-time A* planning with SIPPwRT’s continuous, velocity-aware movements under stated robot and instance assumptions.

TP-SIPPwRT

  • TP-SIPPwRT is complete for well-formed MAPD instances, which have finitely many tasks, at least as many non-task endpoints as agents, and endpoint-to-endpoint paths that avoid other endpoints.The passage states that TP also solves all well-formed instances.Source: TP-SIPPwRT · p. 2
  • TP sends a shared token containing tasks and agent paths to an agent not following a path, which then plans while avoiding conflicts with paths already in the token.The token also ensures no other path uses the agent’s end cell after its end time.Source: TP-SIPPwRT · p. 2
  • TP-SIPPwRT replaces space-time A* with SIPPwRT, which plans continuous forward movements and point turns at given velocities instead of discrete grid moves at uniform velocity.In TP, agents repeatedly plan paths while treating other agents’ paths as dynamic obstacles.Source: TP-SIPPwRT · p. 2
  • Agents are modeled as disks with radius at most half a cell width, moving between cell centers through ninety-degree turns or forward moves; acceleration and deceleration are instantaneous.Collisions are defined by intersection of the interiors of agent disks during movement.Source: TP-SIPPwRT · p. 2

SIPPwRT

SIPPwRT extends safe-interval search to continuous movements with specified velocities, using a reservation table to manage other agents’ paths. Within TP, it plans collision-free paths and preserves completeness for well-formed MAPD instances.

SIPPwRT

  • SIPPwRT replaces discrete, uniform-velocity movements with continuous forward movements and point turns at given velocities.It generalizes safe intervals to maximal contiguous periods when a cell is unoccupied by dynamic obstacles.Source: SIPPwRT · p. 2

Reservation Table and Safe Intervals

  • SIPPwRT’s per-cell reservation table supports safe-interval calculation, adding new path reservations, and deleting reservations from irrelevant past times.Each cell’s priority queue stores occupied intervals in order of their lower bounds.Source: Reservation Table and Safe Intervals · pp. 2–3

Time Offsets

Increased/Decreased Bounds

  • GetLB1 and GetUB1 constrain arrivals and departures around other agents’ visits, while GetLB2 and GetUB2 prevent agents moving in the same direction from passing through one another.The same-direction bounds account for whether the other agent departs before or after the planned agent.Source: Increased/Decreased Bounds · p. 4

Admissible H-Values

  • SIPPwRT uses admissible A* heuristics based on time-minimal paths to endpoints, but uses h(cfg, G) = 0 for TP3 when endpoints are numerous and dense.The zero heuristic is faster to calculate, though SIPPwRT may expand more nodes.Source: Admissible H-Values · p. 4

Pseudocode

  • SIPPwRT searches configuration–safe-interval pairs, generating turn-and-move successors and retaining the earliest feasible arrival within each interval.The algorithm returns a path when it reaches a goal configuration where the agent can wait forever.Source: Pseudocode · pp. 4–5
  • TP-SIPPwRT is complete for well-formed MAPD instances because SIPPwRT provides complete, collision-free single-agent planning for TP1 and TP3.SIPPwRT returns time-minimal paths using admissible heuristics.Source: Pseudocode · p. 5

Simulated Automated Warehouses

The paper evaluates TP-SIPPwRT in simulated warehouse environments and describes how warehouse agents move under different constraints when free or carrying tasks.

  • The agent simulator experiments use small and large simulated warehouse environments.The small environment example has 50 agents; the large environment is used for experiments at larger scales.Source: Simulated Automated Warehouses · p. 5, Figure 3 · p. 6
  • The small warehouse illustration marks potential start cells, randomly selected agent starts, task endpoints, and non-endpoint cells.Source: Simulated Automated Warehouses · p. 6
  • Warehouse agents are modeled as circular robots, with free agents traveling through all cells and task agents restricted to routes that avoid shelf cells.Task agents move through their pickup and delivery endpoints and other non-endpoints.Source: Simulated Automated Warehouses · p. 6

Experimental Results

Across the reported experiments, TP-SIPPwRT is more efficient and effective than the compared MAPD algorithms, and its planning time remains low as agent and task counts increase. A robot-simulator trial also reports safe path following under the tested setup.

Experiment 1: MAPD Algorithms and Task Velocity

  • TP-SIPPwRT has lower service time and makespan and higher throughput than TP-A* and CENTRAL, while requiring less than one second of planning and no post-processing.TP-A* and CENTRAL each require more than 250 seconds of post-processing time.Source: Experimental Results · p. 6
  • TP-SIPPwRT is more effective than TP-A* and CENTRAL in throughput comparisons across task velocities of 0.50, 0.75, and 1.00 m/s.The plotted throughput is tasks completed per second in a moving 100-second window; TP-SIPPwRT's throughput decreases earlier because fewer unexecuted tasks remain toward the end.Source: Experimental Results · p. 6, Figure 4 · p. 7

Experiment 2: Number of Agents, Task Frequency, and Task Velocity

  • Planning time is less than one second for up to 50 agents and 1,000 tasks; service time and makespan decrease and throughput increases as agent count or task velocity increases.The reported service time decreases as task frequency decreases.Source: Experimental Results · p. 7, Table 2 · p. 7

Experiment 3: Environment Size, Number of Agents, and Task Velocity

  • Planning time is less than 16 seconds for up to 250 agents and 2,000 tasks in the large warehouse; service time and makespan decrease as agent count or task velocity increases, with a congestion exception at 250 agents and 1.00 m/s.Throughput and planning time increase with agent count; throughput increases with task velocity.Source: Experimental Results · p. 7, Table 3 · p. 7

Experiment 4: Robot Simulator

  • In the robot simulator, 10 robots safely follow their paths, with a planning time of 2 ms, service time of 90.57 s, and makespan of 171.16 s.The trial uses 20 tasks in the small warehouse environment.Source: Experimental Results · p. 7

Conclusions and Future Work

The conclusion presents TP-SIPPwRT for MAPD and identifies extensions to pathfinding algorithms, robot constraints, and system architecture as future research directions.

  • The paper presents TP-SIPPwRT as an efficient and effective algorithm for the Multi-Agent Pickup and Delivery problem.Source: Conclusions and Future Work · p. 7
  • Future work includes combining SIPPwRT with existing MAPF algorithms, adding acceleration and deceleration constraints, and decentralizing TP-SIPPwRT.The authors note that added kinodynamic constraints could allow robots to follow paths even more safely.Source: Conclusions and Future Work · p. 7

Related papers

Loading 1812.06355v1…