Task Allocation in Multi-Robot Systems: how to meld networks and auction theory in a decentralized way
https://www.researchgate.net/profile/Ivan_Mezei/publication/221207481_Auction_Aggregation_Protocols_for_Wireless_Robot-Robot_Coordination/links/0c96051ac73776f7ae000000/Auction-Aggregation-Protocols-for-Wireless-Robot-Robot-Coordination.pdf
In class, we talked at length about both modelling large numbers of discrete nodes which are connected in specific ways as networks and using auctions to enable individual bidders to compete for a task such that the cost to the bidders for completing a task is optimal for the winning bid. Both auction mechanics and network structure are widely used in creating decentralized sets of agents in a distributed systems setting, and the field of multi-robot systems is one particular application. Multi-robot systems, to summarize, are simply a set of homogenous or heterogeneous robots that are deployed to solve a task through cooperation: think aerial drones searching a disaster zone for survivors and new developments, or a set of rovers sent to map a distant faraway planet. Many of the most promising aspects of multi-robot systems come from their ability to parallelize sensing and task completion in the field: because there are more agents, more tasks can be completed in parallel and certain tasks which could not be completed by one agent could be completed by two working together. Task allocation in multi-robot systems is often conducted in a centralized way: one “commander” robot unilaterally decides which individual agents are best-suited to complete individual tasks, and communicates directly with each external agent to collect data and give commands.
However, this system struggles with one major problem: if certain connections or communications are removed from a robotic network, especially the connection between an agent in the field and the “commander” of the network, how will tasks be assigned efficiently and effectively to each agent? This is where decentralized multi-robot systems come in. Mezei et al, rather than exploiting global communications or connections to a single node, robots can instead use local communications in order to relay and aggregate data to a larger network even if certain, more “centralized” nodes end up failing to communicate (either because of faulty hardware, faulty software, or faulty conditions). Task allocation, rather than being handled centrally, is then handled through a first-price aggregation of auctions: each locally-connected subnetwork of agents conducts a first price auction for a given task that is noticed, calculating “value” based on distance from the task and ability to complete it (whether an agent has the requisite machines or components, whether it has enough energy to manipulate these components, etc.), and aggregating from subnetwork to subnetwork at each time step rather than having each agent submit bids to a single auctioneer.
This especially relates to auctions as discussed in class primarily because, in all cases, every single robot or agent must bid the highest value possible for individual tasks, ensuring that the system will always allocate the most efficient robot to the task at hand. The difference here is that, across an especially large network where individual edges could be removed at any time, auctioning is maintained by splitting the network into clusters grouped mostly by relative distance (i.e. nearby robots form a cluster), creating auctions within each individual cluster, and auctioning the cluster’s auction values (i.e. “aggregation”). The result is a graph that is not only efficient but resilient: after a system is formalized as a graph, removing individual edges in a way that doesn’t completely disconnect the graph ensures that the system still functions as normal. It’s really neat to see seemingly abstract ideas, like auctions and network structure, as greatly embedded into something as physical as a robot, and what’s even more interesting is that the concepts in Networks are often seen in a lot of areas of robotics (especially in the realm of distributed sensing and data flow).