CSCE 689-604: Special Topics in Multi-Robot Systems
Task-Allocation Assignment
In class on February 15 we will have discussed the Optimal Assignment Problem (OAP) in depth, with a focus on the Weighted Bipartite Graph Matching variation of the Hungarian Algorithm. In Gerkey and Mataric's paper, we have seen the relevance of the OAP in task-allocation for SR-ST-IA. In this assignment you are asked to formulate a generalization or extension of the standard OAP, and provide evidence for the usefulness of the proposed idea.
The following are five examples. Any one of these will be adequate for your assignment, however you may also choose some variation along these lines given your own familiarity with techniques involved, and what you can learn about the related material in the time you have available to you. In selecting your problem be sure to consider the evaluation criteria listed below.
1. Generalization: Linear Complementarity Problem
The Linear Programming formulation of the OAP depends on a proof of the constraint matrix being totally unimodular. This permits the Integer Linear Program to be relaxed to Linear Program. The Linear Complementarity Problem (LCP) is a formal problem related to the solution of a linear system, and is related to an optimization problem that is more general than a linear program. Can you identify (after a literature search) whether relaxation is possible in this more general problem? What are the requirements for an assignment-like problem which uses this more general problem underneath? Can you invent an example problem which the LCP-based method permits you to solve that the traditional method does not? What solvers would be available to implement this example problem?
2. Generalization: Convex Optimization and Semi-Definite Programming
The linear programs are among the most widespread scientific computing tools, with many implementations and an efficient run-time in most cases. Techniques of efficient optimization make use of the property of convexity: one consequence is that methods exist which can solve optimization problems significantly more general than linear programs, but at comparable run-times (e.g., essentially O(n3)). Can you identify one instance? Can you provide an implementation that will allow you to solve this instance? Describe how this generality can be useful for a particular set of tasks.
3. Specialization: Multi-robot Routing
This paper describes how a few more iterations of the Hungarian algorithm can be employed to deal with a multi-robot reconfiguration task. If robots have already been deployed throughout an environment (each aware of its current location) then routing new robots to locations on within the group can be done comparatively cheaply, and by employing a single parameter the type of route can be controlled. Are there other problem instances in which give rise to graphs of a particular form so that modifications can be made to the general bipartite matching algorithm? Some examples to consider: edge sparsity, special relationships among utilities (e.g., the difference between a robots' utilities exceeding a minimum value), etc. References in the paper above should also be useful to you.
4. Specialization: Robust Assignments
Generally the task allocation procedure is repeated over and over so as to ensure that robot failures, new task insertions, and update to date information are used in constructing the task assignment. As we read, it is also used to (approximately) address with time extended assignment problems. Assuming repeated assignment occurs and no new tasks are introduced, we wish to understand when robots will reliably maintain their assignments. The alternative is that a robot might, for example, be assigned two different tasks so that it oscillates back and forth never making progress on either of these. Formalize the conditions which ensure this does not happen. Thus, you need to consider the specific means by those factors which contribute to the utility calculation can change.
5. Measurement: Greedy vs. Optimal Assignment
The Gerkey and Mataric' paper gives an optimality gap between the Greedy algorithm and the optimal solution. The quoted gap is a worst-case difference. In many instances, however, the assignment solution computed by both approaches are likely to be identical. If we wish to formalize and measure the ``difficulty'' that a particular assignment problem poses, how might it be done. What are the properties of the metric you've invented?
Submission and Evaluation
This project is due on Feb 22 in either hard- or soft-copy. There is no code or programming expected. It is an individual project. Turn in a report of whatever length you feel necessary but a reasonable guide is: between 2 to 4 pages. You are being assessed on the overall quality of your report: that means that it should be well written, cite sources fully, and acknowledge assistance where used. The strength of the ideas and rigorous, precise mathematical formulation of those ideas, however, are the most important factors. It is important to formalize your description to that it is completely clear. For example, do not just say that the robots perform a `foraging task', but rather specify the properties of each robot, their communication and sensing capabilities mathematically as well as to describe what the objectives of the problem are, and how success can be measured.
An extra 5% credit is given for using LaTeX to typeset your project, and BibTeX for generating the bibliography. (Learn to use these tools now, before your proposals and final reports are due!)