Market-based task allocation in distributed satellite systems
PhD thesis under Dr Jason Noble at the University of Southampton, 2008-2012
This thesis addresses the problem of task allocation in a distributed satellite system. These spacecraft specialise in different functions, and must collaborate to complete the mission objectives. The energy available for task execution and communication is, however, extremely limited, which poses a challenging design problem. I propose the use of a market-based, multi-agent approach to achieve the necessary macro-level behaviour. The development and verification of this allocation mechanism constitutes the first major objective of this thesis. Although numerous examples of task allocation in related systems exist, I found a worrying disconnect between our general, theoretical knowledge of task allocation, and the specific application thereof. General analyses of abstracted task allocation exist, and specific implementations have been constructed in a heuristic way, but very little work navigates between these two extremes. My second major objective therefore contributes to mapping the problem space. The proposed task allocation mechanism is based on human labour markets in order to obtain similar robustness and flexibility. It uses fully distributed auctions to efficiently allocate tasks in volatile networks, without any global knowledge of the system state. The energy required for communication is constant, irrespective of the size of the network, resulting in a highly scalable allocation mechanism.
To find the area in parameter space where market-based control is the more suitable solution, when compared to a centralised approach, I characterised the allocation mechanism in terms of network size, node failure rate, and robustness. The relationship between communication cost and topology is explored by looking at the overheads associated with different static topologies, and the impact of communication distance. The ability of the allocation mechanism to cope with realistic Keplerian dynamics is also confirmed. Finally, I investigate the difference in performance between the allocation mechanism, as an example of a cooperative market, and a competitive scenario where adaptive agents compete to maximise their revenue. Results show that competitive markets are subject to positive feedback loops which can result in inferior performance for sparsely connected and heavily loaded networks.
This exploration of the system parameters is treated as a traversal of the problem space, resulting in an emergent taxonomy of both problem and solution elements.
This project interacts with a number of interesting research fields: complexity science, algorithmic trading, multi-agent systems
Changing network topology as satellites orbit around the earth. As spacecraft move further apart, communication links are broken, changing the routes required to manage the network.
A Google scholar list of publications can be found here.