Information Technology Reference
In-Depth Information
can cheaply pick up another load at fruitful region F 2 or F 3 , as this fits in its
current planned route, but it will have to make a costly detour to pick up a load
l originating in region F 1 .
In our experiments, we consider agents making one round trip starting from
the depot D and visiting each fruitful region F i only if at least one load has been
won in an auction. The agents only pick up their cargo after all the auctions are
finished. Without taking into account movement costs, the valuation is equal to
1 for every load from each and every region for each and every agent. In this
initial setting, there are as yet no complementarity issues.
However, we impose a movement cost of 0 . 25 from the depot D to any fruitful
region and a movement cost of 0 . 5 between any two fruitful regions. The straight-
forward valuation for a new load l 1 of fruitful region F i is hence 0 . 5 if an agent
a has not yet won any loads for that fruitful region. A second load l 2 won from
F i will then yield a straightforward valuation of 1 as no extra movement costs
are required to incorporate the pickup of l 2 . There is hence a complementary
valuation between l 1 and l 2 which can give an incentive for a to bid more than
0 . 5for l 1 to increase the changes of winning l 2 , and further loads from this same
fruitful region. Let agent a have won loads L =
where L i are
the loads won in fruitful region F i . We define the immediate valuation of agent
a for a new load l from fruitful region F k as 0 . 5if
{
L 1 ,L 2 ,...,L n }
= 0 and as 1 otherwise.
The state of the agent agent i during the auctions is, in part, characterized by
the number of auctions won for each fruitful region, limited by the capacity of
the agent. In Figure 1b we show the possible states for an agent with capacity
2 bidding in auctions for loads originating in one of n = 2 fruitfulregions. The
agent starts with 0 loads acquired ((0 , 0)) and moves to consecutive states as
it wins loads in auctions. The immediate valuation is given for the transitions
between states. For a state s and a load l from fruitful region F i ,wecallthe
new state s a successor of s for l . For example, in Figure 1b, state (0 , 1) is a
successor of state (0 , 0) for a load l from fruitful region F 2 . In a logistics domain,
fruitful regions are useful, realistic abstractions that allow us to reduce a large,
fine-grained world to a few abstract points of interest. This allows us to define
a compact state space as a function of the number of loads acquired per fruitful
region.
In each of the sequential auctions Auctions =
|
L k |
,one
load from one of the fruitful regions is sold. Hence the number of auctions
t = Σ i F i . For each auction, one random load from any of the remaining loads is
chosen. The agents know the number of auctions, they know the initial number
of loads available a priori for each fruitful region, but they do not know the
bidding strategies of their opponents and the specific order in which the loads
will be auctioned. The agents participate in many repeated epochs of such se-
quential auctions. After each epoch, the order in which the loads are auctioned
are randomized anew. At the end of each epoch, agents can adjust their bidding
strategy.
The question is whether an agent can formulate a bidding strategy that can
exploit the complementary values in the domain. I.e, can an agent formulate a
{
auction 1 ,...,auction t }
Search WWH ::




Custom Search