## 3 Dynamic Multi-Objective (DYMO) Auction-Based Task Allocation
### Auction Process  
The auction process is the main component of the market-based task allocation approach; robots cooperate via an explicit negotiation. The proposed method uses a low-cost one-round single auction, meaning that a task is assigned to the robot with the lowest bid in one round. Robots bid by their cost to execute the task. The auction process consists of four sequential steps.  
1. Task advertisement: The auction process starts once a robot discovers a new task or receives an advertisement message from an agent outside the system (e.g., a remote-sensing system in automated farming applications). It is worth noting that any robot can act as an auctioneer. The auctioneer is not pre-selected; instead, for each new task, the sensor system that detects a new task, it selects a robot randomly. The task advertisement message includes all the details of the task (i.e., location, quality level, and the required resources). The robot that receives the task's details will consider itself the auctioneer for that particular task.
2. Auction announcement: Then, the auctioneer computes its bid for the task and announces a new auction by broadcasting an auction message auctionMsg to its neighbors. The auction announcement message contains all the details of the current tasks. The auction remains open for a sufficient amount of time to allow bidders to send their bids.
3. Bid submission: Once a robot receives an auction announcement message, it computes its bid based on the proposed cost function and submits it to the auctioneer. Unlike the conventional auction-based bidding process, in which a robot computes its bid based only on the distance. The proposed approach considers the distance, quality satisfaction, and workload balance. A bid is a scalar value computed using the cost function and represents a robot's cost to execute the task. The cost function design is explained in the next section.
4. Closing the auction and winner selection: During the auction, the auctioneer maintains a list, BidsList, of all current bids and the associated bidders' IDs; then, once the auction time ends, it selects the bidder with the minimum bid (cost) from the bids list BidsList and assigns it the current task.  
Figure 3 contrasts the state machine of a robot during the auction process. Initially, robots start in an idle state, and if a robot receives a task advertisement, it moves to the auctioneer state. In the auctioneer state, a robot computes its bid and opens a new auction for the task, as shown in Algorithm 1. All robots that receive the \(auctionMsg\) change from the idle state to the bidder state and run Algorithm 2, in which they compute their cost and send it to the auctioneer. The auctioneer then selects the winning bidder and sends it the task assignment message \(winMsg\). After the task has been assigned, all robots, both the auctioneer and bidders, return to the idle state again.  
```
input :New task announcement output :Assigning a task to the highest bidder
1 AuctioneerBid \(\leftarrow\) ComputeMyBid();
2 AppendToBidsList(AuctioneerId,AuctioneerBid) ;
3 BroadcastAuctionMsg();
4 AuctioneerTimer \(\gets\)\(t\)\(sec\);
5 while!IsAuctionEnds()do
6 ifReceiveBidMsg()then
7 AppendToBidsList(_bidValue,BidderID_) ;
8 winnerBidder \(\leftarrow\)GetHighestBidder();
9 SendTaskAssignMsg(winnerBidder);
```  
**Algorithm 1**Auctioneer algorithm  
```
input :Auction message, Task Assignment message output :Bid for task, append assigned task to the task list
1 In parallel with other procedures;
2 ifAuctionMsgReceived()then
3 MyBid \(\leftarrow\)ComputeMyBid() ;
4 sendBidMsg (MyBid,auctioneerID);
5 elseifTaskAssignMsgReceived()then
6 AppendToTaskList(_NewTask_);
```  
**Algorithm 2**Bidder algorithm