Task Allocation Method and System for Two Heterogeneous Robots

Task Allocation Technology for Two Heterogeneous Robots Based on Primal-Dual Heuristics

This technology is a task allocation method and system that applies primal-dual heuristics to distribute tasks between two structurally heterogeneous robots, iteratively adjusting cost weights for each robot to minimize the maximum total travel cost.

Existing challenges included the difficulty of achieving efficient task allocation and path planning to balance task completion times and minimize the maximum travel cost of the entire system in environments where the two robots have different performance capabilities.

This technology proposes a method that assigns weights to each robot's travel cost, distributes destinations using primal-dual heuristics, and then adjusts the weights to reduce the higher value by comparing the calculated total travel costs to derive an optimal path. It provides a practical solution for significantly reducing total task completion time in environments where robots with different performance levels coexist, such as logistics warehouses, factory automation, and disaster prevention patrols.

‍

‍

Key Features:

• Weight registration step where cost weights for each heterogeneous robot are registered
• Destination allocation step where multiple destinations are distributed to each robot using primal-dual heuristics
• Path planning step where the allocated destinations are applied to a path planning algorithm to calculate travel routes and total travel costs
• Configuration that iteratively adjusts cost weights to reduce the higher value among the total travel costs

‍

This invention was developed with support from the National Research Foundation of Korea for the Intelligent Growth Autonomous Driving System for Unmanned Vehicles Operating Safely in Congested Residential Road Environments.