The long-term maintenance of deep-space habitats requires the ability to dynamically allocate spatio-temporal tasks and robustly handle their execution. A centralized framework becomes infeasible in this setting, as the planning space can become intractable over long-term horizons, as well as the fact that single-point failures may be common and hard to recover from. Thus we utilize a decentralized, market-based approach to solve the multi-agent task allocation problem. To respect temporal constraints, we utilize STNs as a core component of each agent's execution monitoring and scheduling mechanism. We then conduct a comparison of single-agent versus multi-agent re-planning mechanisms, and identify the contexts in which each may outperform the other. We also introduce a novel positive re-planning technique that utilizes a reverse-allocation auction mechanism to match tasks to slots. Ultimately, we find that when optimizing for makespan, the multi-agent approach consistently beats the single-agent one. However, when optimizing for certain metrics such as travel time, the single-agent can fare better in specific environments. Therefore, we conclude that the multi-agent approach is better suited for the deep-space domain, suggesting that more work could be done by considering alternate objective functions.

35 pages

Thesis Committee:
Stephen F. Smith (Chair)
Zachary Rubinstein

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu