Solving the task variant allocation problem in distributed robotics

Area of Science:

• Robotics
• Software Engineering
• Operations Research

Background:

• Distributed robotics systems require efficient task assignment to hardware processors.
• Adapting software to diverse hardware configurations is a key challenge.
• Existing methods may not adequately balance functional quality with hardware constraints.

Purpose of the Study:

• To introduce and formalize the concept of task variants for adaptable software in robotics.
• To develop and evaluate mathematical models and solution methods for task variant assignment.
• To demonstrate the practical benefits of task variants and proposed methods in a real-world multi-agent system.

Main Methods:

• Formalized task variant assignment as a constrained multi-objective, multi-dimensional, multiple-choice knapsack problem.
• Developed and compared three solution methods: constraint programming, greedy heuristic, and local search metaheuristic.
• Evaluated methods using a distributed interactive multi-agent navigation system.

Main Results:

• Constraint programming outperformed other methods, achieving an average quality of service improvement of 16% over local search, 31% over greedy heuristic, and 56% over a randomized solution.
• Task variants effectively enable trade-offs between functional quality and hardware resource utilization.
• The mathematical model accurately represents constraints typical in robotics applications.

Conclusions:

• Task variants are a valuable concept for enhancing software adaptability in distributed robotic systems.
• Constraint programming provides a superior solution for the task variant assignment problem compared to heuristics.
• The proposed approach demonstrably improves the quality of service in complex robotic applications like multi-agent navigation.