Only released in EOL distros:   fuerte

This stack is dedicated to auction methods.

At this moment there are implemented 4 protocols, Simple Auction Protocol (SAP), k-hop Simple Auction Protocol (k-SAP), Simple Aggregation Auction Protocol (SAAP) and k-hop Simple Aggregation Auction Protocol (k-SAAP)

Documentation

Introduction

A multi-robot system (MRS) (Parker2008) is defined as a variable sized group of robots that operate in the same environment. This definition can lead to a misconception if an MRS is considered to be the generalized view of a single robot. In fact, the concept of an MRS implies the existence of an internal organization intended to achieve coordination and cooperation.

In general terms in an MRS each robot must follow a set of requirements, such as:

• must be capable of sensing and acting according to changes in a dynamic and uncertain environment;
• must have a flexible behaviour with reactive and deliberative actions;
• must be autonomous;
• must be mobile.

In an MRS it is commonly assumed that the group of robots share the same environment and mission. These two constraints (i.e. environment and mission) can differ in complexity and magnitude. By complexity, we consider the intelligibility of the task and by magnitude the size in terms of duration or task space. Depending on these two constraints the MRS can be proposed as more adequate. For instance, an MRS is usually advantageous for tasks that require a great space distribution, parallel execution. Additionally, the reliability and robustness of this type of system are often greater than for a single-robot approach, given that generally simpler robots are used, and that we have redundancy in the system. Consequently, MRS will have lower cost by unit compared to the single-robot system. There are many application domains for MRS, some examples are high-risk scenarios like search and rescue and repetitive missions like industrial autonomous stackers performing pick and place tasks in a lumber mill.

Coordination and Cooperation

Coordination is defined as making different people or things work together for a goal or effect to fulfil desired goals in an organization and cooperation is defined as the process by which the components of a system work together to achieve the global properties. In other words, individual components that appear to be "selfish" and independent work together to create a highly complex, greater-than-the-sum-of-its-parts system. Thus, coordination is an orderly arrangement of efforts to provide unity of action in the fulfilment of common objective whereas cooperation denotes collective efforts for the achievement of a particular purpose. It is the willingness of individuals to help each other. Coordination is an effort to integrate effectively energies of different groups whereas cooperation is the sort to achieve general objectives of the business. Though these two are synonymous we can identify some differences regarding the meaning, the scope, the process, the requirements, the relationship between individuals, freedom of actions, and support as expressed in the table below.

Differences between coordination and cooperation

Auction Protocols

In general terms, an auction process (i.e. the negotiation process) is triggered when a task is inserted in the system (through a human operator, a task generator or as a consequence of a previous task). The steps of the auction protocol are the following: First, one of the agents, related to the task insertion system, acts as the auctioneer and sends a message announcing the new task. The auction message contains detailed information related to the task. Second, each robot that received the message will evaluate it, computing the cost to offer its service. Third, each competing robot will communicate to the auctioneer its cost, as a bid message. Fourthly, the auctioneer compares the received bids and declares a winner.

Simple Auction Protocols

In the SAP approaches, the auction follows the first-price sealed-bid type. Therefore, blind bids are used. Explicit consideration of localized auctions in multi-hop scenarios was first proposed in (Melodia2007) for single task single robot assignment. It is a localized solution for actor-actor coordination based on 'localized auction protocol'. In the scenarios considered in our study, the event emulates the sensor action, when it detects a change in the environment and notifies an agent or a robot, hereby designated by the node. The notified node will assume the auctioneer role and broadcast an auction message to the neighbour nodes, which will assume buyer roles. This process is usually known as network flooding. In SAP protocols each buyer responds back to the auctioneer using a separate route, with the offer to provide service and the cost of doing it. In our scenarios, we simulated blind flooding, which is used for node search. In this method, each node retransmits the request upon receiving it for the first time and ignores it afterwards. These type of protocols can always find the closest node to the event since all agents are consulted. However, the response time can be large if the best node is near the event, but the network is large and the responses from all nodes are gathered before a decision is made. In multi-hop networks could be advantageous, instead of flooding the whole network, searching for bids only among nodes located up to k hops away from auctioneer node. This protocol applies limited flooding (only up to k-hop neighbours), and it is designated by k-SAP. The k-SAP represents an improved extension to SAP.

Simple Auction Aggregation Protocols

Another improvement over SAP, in terms of communication overhead reduction, is the use of auction aggregation protocols (Mezei2010). In these methods, instead of using separate routing tasks, the constructed tree, during information phase, can be used for reporting back. The SAAP protocols have tree ‘expansion’ and tree ‘contraction’ phases. Tree expansion starts from the auctioneer node by creating a tree rooted at the auctioneer. Retransmissions from the descendent nodes create a response tree. Each node, with retransmission, includes ID of its parent node in the message, so that nodes can locally decide whether or not they are leaves in the created tree. Note that each node selects only one parent, in case of multiple received bids. The nodes become leaves if they do not retransmit the bid or do not hear any other node listing them as their parent. The described approach is known as SAAP (simple auction aggregation protocol). In case of limited flooding in a multi-hop network, it is called k-SAAP. The differences between SAAP and SAP (and similarly between k-SAAP and k-SAP) is that individual bids are aggregated at intermediate nodes, instead of routing all of them back to the auctioneer node.

Demonstration Video

Tutorials

Please refer to here.