IEEE Robotics & Automation Magazine - December 2010 - 67
to k-hops away from bidding robot. This protocol applies
limited flooding (only up to k-hop neighbors), and it will
be designated as k-SAP. In example in Figure 4, 1-SAP
will gather bids only from R2 and R3, and thus, the best
bid from R4 is not considered; 2-SAP will flood from R1,
R2, R4, R3, R8, and R5 robots; 3-SAP will consult all
the robots.
Another improvement of SAP in terms of communication
overhead reduction is the use of the AAP. Instead of using
separate routing tasks, the constructed tree can be used for
reporting back. The protocol has tree expansion and tree contraction phases. Tree expansion starts from collecting robot
R1 by creating a tree rooted at R1 (see Figure 4). Retransmissions create a response tree. Each node, with retransmission,
includes identification number of its parent robot in the
message so that robots 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 (e.g., R9 is
joined only to R4). They become leaves if they do not
retransmit the bid or do not hear any other robot listing them
as their parent.
Leaf nodes start responding back to parent robots, with
the best cost they are aware of. This is in fact auction aggregation and, thus, reduces the number of messages in the bidding phase. Each intermediate node waits to hear from all its
neighbors, which declared it as a parent, thus becoming a
local collector. After hearing, they select the best cost and
report further toward the collector. At the end, the collector
decides which robot is the best to perform the required
action and routes the decision to that robot. In the example
in Figure 4, robots R5, R6, R7, R8, and R9 are leaves in
the created tree and return their bids to their parent nodes.
R4 returns to its parent R2, its own bid as the best it is aware
off; similarly, R3 also returns its own bid. R2 returns to R4
as the best bidder. The root node (R1) then selects the best
bid (in this case, from R4) from the two received offers and
delivers the task to R4 along the created path of R1-R2-
R4. This version of AAP will be designated as simple AAP
(SAAP). In the case of limited flooding (only up to k-hop
neighbors from the collector), it is called k-SAAP. The difference between k-SAAP and k-SAP (and similarly between
SAP and SAAP) is that individual bids are aggregated at
intermediate nodes, instead of routing all of them back to
the collector robot.
Providing autonomy in retransmitting decisions to individual robots can further refine the algorithm. In k-SAAP, the
receiving robot will retransmit only if it is at a distance
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - December 2010
IEEE Robotics & Automation Magazine - December 2010 - Cover1
IEEE Robotics & Automation Magazine - December 2010 - Cover2
IEEE Robotics & Automation Magazine - December 2010 - 1
IEEE Robotics & Automation Magazine - December 2010 - 2
IEEE Robotics & Automation Magazine - December 2010 - 3
IEEE Robotics & Automation Magazine - December 2010 - 4
IEEE Robotics & Automation Magazine - December 2010 - 5
IEEE Robotics & Automation Magazine - December 2010 - 6
IEEE Robotics & Automation Magazine - December 2010 - 7
IEEE Robotics & Automation Magazine - December 2010 - 8
IEEE Robotics & Automation Magazine - December 2010 - 9
IEEE Robotics & Automation Magazine - December 2010 - 10
IEEE Robotics & Automation Magazine - December 2010 - 11
IEEE Robotics & Automation Magazine - December 2010 - 12
IEEE Robotics & Automation Magazine - December 2010 - 13
IEEE Robotics & Automation Magazine - December 2010 - 14
IEEE Robotics & Automation Magazine - December 2010 - 15
IEEE Robotics & Automation Magazine - December 2010 - 16
IEEE Robotics & Automation Magazine - December 2010 - 17
IEEE Robotics & Automation Magazine - December 2010 - 18
IEEE Robotics & Automation Magazine - December 2010 - 19
IEEE Robotics & Automation Magazine - December 2010 - 20
IEEE Robotics & Automation Magazine - December 2010 - 21
IEEE Robotics & Automation Magazine - December 2010 - 22
IEEE Robotics & Automation Magazine - December 2010 - 23
IEEE Robotics & Automation Magazine - December 2010 - 24
IEEE Robotics & Automation Magazine - December 2010 - 25
IEEE Robotics & Automation Magazine - December 2010 - 26
IEEE Robotics & Automation Magazine - December 2010 - 27
IEEE Robotics & Automation Magazine - December 2010 - 28
IEEE Robotics & Automation Magazine - December 2010 - 29
IEEE Robotics & Automation Magazine - December 2010 - 30
IEEE Robotics & Automation Magazine - December 2010 - 31
IEEE Robotics & Automation Magazine - December 2010 - 32
IEEE Robotics & Automation Magazine - December 2010 - 33
IEEE Robotics & Automation Magazine - December 2010 - 34
IEEE Robotics & Automation Magazine - December 2010 - 35
IEEE Robotics & Automation Magazine - December 2010 - 36
IEEE Robotics & Automation Magazine - December 2010 - 37
IEEE Robotics & Automation Magazine - December 2010 - 38
IEEE Robotics & Automation Magazine - December 2010 - 39
IEEE Robotics & Automation Magazine - December 2010 - 40
IEEE Robotics & Automation Magazine - December 2010 - 41
IEEE Robotics & Automation Magazine - December 2010 - 42
IEEE Robotics & Automation Magazine - December 2010 - 43
IEEE Robotics & Automation Magazine - December 2010 - 44
IEEE Robotics & Automation Magazine - December 2010 - 45
IEEE Robotics & Automation Magazine - December 2010 - 46
IEEE Robotics & Automation Magazine - December 2010 - 47
IEEE Robotics & Automation Magazine - December 2010 - 48
IEEE Robotics & Automation Magazine - December 2010 - 49
IEEE Robotics & Automation Magazine - December 2010 - 50
IEEE Robotics & Automation Magazine - December 2010 - 51
IEEE Robotics & Automation Magazine - December 2010 - 52
IEEE Robotics & Automation Magazine - December 2010 - 53
IEEE Robotics & Automation Magazine - December 2010 - 54
IEEE Robotics & Automation Magazine - December 2010 - 55
IEEE Robotics & Automation Magazine - December 2010 - 56
IEEE Robotics & Automation Magazine - December 2010 - 57
IEEE Robotics & Automation Magazine - December 2010 - 58
IEEE Robotics & Automation Magazine - December 2010 - 59
IEEE Robotics & Automation Magazine - December 2010 - 60
IEEE Robotics & Automation Magazine - December 2010 - 61
IEEE Robotics & Automation Magazine - December 2010 - 62
IEEE Robotics & Automation Magazine - December 2010 - 63
IEEE Robotics & Automation Magazine - December 2010 - 64
IEEE Robotics & Automation Magazine - December 2010 - 65
IEEE Robotics & Automation Magazine - December 2010 - 66
IEEE Robotics & Automation Magazine - December 2010 - 67
IEEE Robotics & Automation Magazine - December 2010 - 68
IEEE Robotics & Automation Magazine - December 2010 - 69
IEEE Robotics & Automation Magazine - December 2010 - 70
IEEE Robotics & Automation Magazine - December 2010 - 71
IEEE Robotics & Automation Magazine - December 2010 - 72
IEEE Robotics & Automation Magazine - December 2010 - 73
IEEE Robotics & Automation Magazine - December 2010 - 74
IEEE Robotics & Automation Magazine - December 2010 - 75
IEEE Robotics & Automation Magazine - December 2010 - 76
IEEE Robotics & Automation Magazine - December 2010 - 77
IEEE Robotics & Automation Magazine - December 2010 - 78
IEEE Robotics & Automation Magazine - December 2010 - 79
IEEE Robotics & Automation Magazine - December 2010 - 80
IEEE Robotics & Automation Magazine - December 2010 - 81
IEEE Robotics & Automation Magazine - December 2010 - 82
IEEE Robotics & Automation Magazine - December 2010 - 83
IEEE Robotics & Automation Magazine - December 2010 - 84
IEEE Robotics & Automation Magazine - December 2010 - 85
IEEE Robotics & Automation Magazine - December 2010 - 86
IEEE Robotics & Automation Magazine - December 2010 - 87
IEEE Robotics & Automation Magazine - December 2010 - 88
IEEE Robotics & Automation Magazine - December 2010 - 89
IEEE Robotics & Automation Magazine - December 2010 - 90
IEEE Robotics & Automation Magazine - December 2010 - 91
IEEE Robotics & Automation Magazine - December 2010 - 92
IEEE Robotics & Automation Magazine - December 2010 - 93
IEEE Robotics & Automation Magazine - December 2010 - 94
IEEE Robotics & Automation Magazine - December 2010 - 95
IEEE Robotics & Automation Magazine - December 2010 - 96
IEEE Robotics & Automation Magazine - December 2010 - 97
IEEE Robotics & Automation Magazine - December 2010 - 98
IEEE Robotics & Automation Magazine - December 2010 - 99
IEEE Robotics & Automation Magazine - December 2010 - 100
IEEE Robotics & Automation Magazine - December 2010 - 101
IEEE Robotics & Automation Magazine - December 2010 - 102
IEEE Robotics & Automation Magazine - December 2010 - 103
IEEE Robotics & Automation Magazine - December 2010 - 104
IEEE Robotics & Automation Magazine - December 2010 - 105
IEEE Robotics & Automation Magazine - December 2010 - 106
IEEE Robotics & Automation Magazine - December 2010 - 107
IEEE Robotics & Automation Magazine - December 2010 - 108
IEEE Robotics & Automation Magazine - December 2010 - 109
IEEE Robotics & Automation Magazine - December 2010 - 110
IEEE Robotics & Automation Magazine - December 2010 - 111
IEEE Robotics & Automation Magazine - December 2010 - 112
IEEE Robotics & Automation Magazine - December 2010 - 113
IEEE Robotics & Automation Magazine - December 2010 - 114
IEEE Robotics & Automation Magazine - December 2010 - 115
IEEE Robotics & Automation Magazine - December 2010 - 116
IEEE Robotics & Automation Magazine - December 2010 - 117
IEEE Robotics & Automation Magazine - December 2010 - 118
IEEE Robotics & Automation Magazine - December 2010 - 119
IEEE Robotics & Automation Magazine - December 2010 - 120
IEEE Robotics & Automation Magazine - December 2010 - Cover3
IEEE Robotics & Automation Magazine - December 2010 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2010
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2010
https://www.nxtbookmedia.com