Heuristically Guided Compilation for Task Assignment and Path Finding

We investigate the Combined Target-Assignment and Path-Finding (TAPF) problem that computes both task assignments and collision-free paths for multiple agents, that is, each agent is required to select a target from an underlying set, reaching which leads to a payoff. There is a cost closely related to the time required for each agent to reach the goal. The objective is to maximize the minimum gain generated by the agents. We proposed a Compilation-Based Approach with Heuristics (TA-CBWH) to approximate the optimal solution, behind which are two critical ideas: (i) for a specific task assignment, we formulate an integer linear programming (ILP) and create the iteration combined with large neighborhood search (LNS) to quickly improve the solution quality to near-optimal; (ii) regarding distinct task assignments, a switching mechanism is developed to determine the most promising iteration while progressively eliminating unnecessary task assignments. Comparative experiments demonstrate that TA-CBWH outperforms a wide range of existing approaches across various maps and different numbers of agents.

Authors

• Zheng Chen
• Changlin Chen
• Yiran Ni
• Junhao Wang

Keywords

• Machine learning algorithms
• Costs
• Heuristic algorithms
• Switches
• Machine learning
• Integer linear programming
• Linear programming
• Iterative methods
• Robotics and automation
• Pathfinding
• Number Of Agents
• Solution Quality
• Specific Assignment
• Value Function
• Convergence Rate
• Feasible Solution
• Minimization Problem
• Local Setting
• Objective Value
• Path Planning
• Feasible Set
• Penalty Function
• Heuristic Search
• Saddle Point
• Maximization Problem
• Number Of Assignments
• Neighborhood Size
• Near-optimal Solution
• Assignment Of Values
• Makespan
• Collision Happens
• Threshold Interval
• Start Location
• Goal Of The Agent
• Undirected
• Iterative Process
• Time Step
• Conflict Resolution