We consider the problem of tracking multiple moving robots using noisy sensing of inter-robot and inter-beacon distances. Sensing is local: there are three fixed beacons at known locations, so distance and position estimates propagate across multiple robots. We show that the technique of Nonparametric Belief Propagation (NBP), a graph-based generalization of particle filtering, can address this problem and model multi-modal and ring-shaped uncertainty distributions. NBP provides the basis for distributed algorithms in which messages are exchanged between local neighbors. Generalizing previous approaches to localization in static sensor networks, we improve efficiency and accuracy by using a dynamics model for temporal tracking. We compare the NBP dynamic tracking algorithm with SMCL+R, a sequential Monte Carlo algorithm. Whereas NBP currently requires more computation, it converges in more cases and provides estimates that are 3 to 4 times more accurate. NBP also facilitates probabilistic models of sensor accuracy and network connectivity.

Large-scale sensor network applications require in-network processing and data fusion to compute statistically relevant summaries of the sensed measurements. This paper studies distributed message-passing algorithms, in which neighboring nodes in the network pass local information relevant to a global computation, for performing statistical inference. We focus on the class of reweighted belief propagation (RBP) algorithms, which includes as special cases the standard sum-product and max-product algorithms for general networks with cycles, but in contrast to standard algorithms has attractive theoretical properties (uniqueness of fixed points, convergence, and robustness). Our main contribution is to design and implement a practical and modular architecture for implementing RBP algorithms in real networks. In addition, we show how intelligent scheduling of RBP messages can be used to minimize communication between motes and prolong the lifetime of the network. Our simulation and Mica2 mote deployment indicate that the proposed algorithms achieve accurate results despite real-world problems such as dying motes, dead and asymmetric links, and dropped messages. Overall, the class of RBP provides provides an ideal fit for sensor networks due to their distributed nature, requiring only local knowledge and coordination, and little requirements on other services such as reliable transmission.

To address privacy concerns with digital video surveillance cameras, we propose a practical, real-time approach that preserves the ability to observe actions while obscuring individual identities. In our proposed respectful cameras system, people who wish to remain anonymous agree to wear colored markers such as a hat or vest. The system automatically tracks these markers using statistical learning and classification to infer the location and size of each face and then inserts elliptical overlays. Our objective is to obscure the face of each individual wearing a marker, while minimizing the overlay area in order to maximize the remaining observable region of the scene. Our approach incorporates a visual color-tracker based on a 9 dimensional color-space by using a probabilistic AdaBoost classifier with axis-aligned hyperplanes as weak-learners. We then use particle filtering to incorporate interframe temporal information. We present experiments illustrating the performance of our system in both indoor and outdoor settings, where occlusions, multiple crossing targets, and lighting changes occur. Results suggest that the respectful camera system can reduce false negative rates to acceptable levels (under 2%).

This article considers a canonical auction protocol that forms the basis of nearly all current online auctions. Such discrete bid auctions require that the bidders submit bids at predetermined discrete bid levels, and thus, there exists a minimal increment by which the bid price may be raised. In contrast, the academic literature of optimal auction design deals almost solely with continuous bid auctions. As a result, there is little practical guidance as to how an auctioneer, seeking to maximize its revenue, should determine the number and value of these discrete bid levels, and it is this omission that is addressed here. To this end, a model of an ascending price English auction with discrete bid levels is considered. An expression for the expected revenue of this auction is derived and used to determine numerical and analytical solutions for the optimal bid levels in the case of uniform and exponential bidder's valuation distributions. Finally, in order to develop an intuitive understanding of how these optimal bid levels are distributed, the limiting case where the number of discrete bid levels is large is considered, and an analytical expression for their distribution is derived.

We present a mathematical model of the eBay auction protocol and perform a detailed analysis of the effects that the eBay proxy bidding system and the minimum bid increment have on the auction properties. We first consider the revenue of the auction, and we show analytically that when two bidders with independent private valuations use the eBay proxy bidding system there exists an optimal value for the minimum bid increment at which the auctioneer's revenue is maximized. We then consider the sequential way in which bids are placed within the auction, and we show analytically that independent of assumptions regarding the bidders' valuation distribution or bidding strategy the number of visible bids placed is related to the logarithm of the number of potential bidders. Thus, in many cases, it is only a minority of the potential bidders that are able to submit bids and are visible in the auction bid history (despite the fact that the other hidden bidders are still effectively competing for the item). Furthermore, we show through simulation that the minimum bid increment also introduces an inefficiency to the auction, whereby a bidder who enters the auction late may find that its valuation is insufficient to allow them to advance the current bid by the minimum bid increment despite them actually having the highest valuation for the item. Finally, we use these results to consider appropriate strategies for bidders within real world eBay auctions. We show that while last-minute bidding (sniping) is an effective strategy against bidders engaging in incremental bidding (and against those with common values), in general, delaying bidding is disadvantageous even if delayed bids are sure to be received before the auction closes. Thus, when several bidders submit last-minute bids, we show that rather than seeking to bid as late as possible, a bidder should try to be the first sniper to bid (i.e., it should “snipe before the snipers”).

In this paper we consider a common form of the English auction that is widely used in online Internet auctions. This discrete bid auction requires that the bidders may only submit bids which meet some predetermined discrete bid levels and, thus, there exists a minimal increment with which a bidder may raise the current price. In contrast, the academic literature of optimal auction design deals almost solely with continuous bid auctions, and, as a result, there is little practical guidance as to how an auctioneer, who is seeking to maximise his revenue, should determine the number and value of these discrete bid levels. Consequently, in current online auctions, a fixed bid increment is commonly implemented, despite this having been shown to be optimal in only limited cases.Given this background, in this paper, our aim is to provide the optimal auction design for an English auction with discrete bid levels. To this end, we derive an expression that relates the expected revenue of the auction, to the actual discrete bid levels im-plemented, the number of bidders participating, and the distribution from which the bidders draw their private independent valuations. We use this expression to derive numerical and analytical solutions for the optimal bid levels in the general case. To compare these results with previous work, we apply these solutions to an example, where bidders' valuations are drawn from a uniform distribution. In this case, we prove that when there are more than two bidders, a decreasing bid increment is optimal and we show that the optimal reserve price of the auction increases as the number of bidders increases. Finally, we compare the properties of an auction in which optimal bid levels are used, to the standard auction approach which implements a fixed bid increment. In so doing, we show that the optimal bid levels result in improvements in the revenue, duration and allocative efficiency of the auction.