12614052
Learning haptic feedback for guiding driver behavior
Information about the driving state can be conveyed to automobile drivers through force feedback signals sent via the pedals and steering wheel. Because the set of possible haptic signals and driver responses is huge, it is desirable to automatically learn which signals are most useful to drivers. Thus, it is instructive to explore how machine learning techniques can be used as a step in the design of a haptic interface system. In this paper, we present a learning algorithm that learns useful haptic feedback and apply the algorithm to learning feedback for automobile drivers. We present evidence to show that the algorithm is sensitive enough to learn useful feedback under some circumstances, but that its scope may be limited by people's ability to act as admittance controllers.
15752591
Satisficing anytime action search for behavior-based voting
Within the field of behavior-based robotics, a useful and popular technique for robot control is that of utilitarian voting, where behaviors representing objectives assign utilities to candidate actions. Utilitarian voting allows for distributed, modular control but is not well suited to systems with very high resolution or several, dependent degrees of freedom. Past systems have depended on exhaustive searches that choose the action with the highest combined utility. We present, instead, a framework that casts the action search problem as an anytime algorithm. This allows directed searches to be used with time limit constraints. Aspiration-based satisficing additionally helps to reduce CPU usage. In experiments so far, we have decreased CPU usage by UP to 42% while causing result quality to be no more than 6% worse.
11363478
Learning To Cooperate in a Social Dilemma: A Satisficing Approach to Bargaining
Learning in many multi-agent settings is inherently repeated play. This calls into question the naive application of single play Nash equilibria in multi-agent learning and suggests, instead, the application of give-and-take principles of bargaining. We modify and analyze a satisficing algorithm based on (Karandikar et al., 1998) that is compatible with the bargaining perspective. This algorithm is a form of relaxation search that converges to a satisficing equilibrium without knowledge of game payoffs or other agents' actions. We then develop an M action, N player social dilemma that encodes the key elements of the Prisoner's Dilemma. This game is instructive because it characterizes social dilemmas with more than two agents and more than two choices. We show how several different multi-agent learning algorithms behave in this social dilemma, and demonstrate that the satisficing algorithm converges, with high probability, to a Pareto efficient solution in self play and to the single play Nash equilibrium against selfish agents. Finally, we present theoretical results that characterize the behavior of the algorithm.
14885043
Sorting on a parallel pointer machine with applications to set expression evaluation
We present optimal algorithms for sorting on parallel CREW and EREW versions of the pointer machine model. Intuitively, one can view our methods as being based on a parallel mergesort using linked lists rather than arrays (the usual parallel data structure). We also show how to exploit the “locality” of our approach to solve the set expression evaluation problem, a problem with applications to database querying and logic-programming in <italic>O</italic>(log <italic>n</italic>) time using <italic>O</italic>(<italic>n</italic>) processors. Interestingly, this is an asymptotic improvement over what seems possible using previous techniques.
15633793
Efficient perspective-accurate silhouette computation
Silhouettes of geometric models (see Fig.1) are salient for many applications, including visualization [LE97] and shape analysis [BV95, Cro77]. The video describes a technique for efficient tracking of perspective-accurate silhouettes by reducing the problem to point location queries. Perspective-accurate silhouette computation is known to be difficult [KM96, KM98, KMGL96]. Note that silhouettes formed under perspective projection are significantly different from those under parallel projection and are more difficult to compute. Given a polyhedral model with well-defined normals, the polygons (facets) whose normals point away from the viewpoint are called back-facing. Similarly, normals of front-facing polygons point toward the viewpoint. An edge shared by a back-facing polygon and a front-facing polygon is said to be on the silhouette of the model. The silhouette of a geometric model is among its most significant visual features. It may be used to describe the shape of a model with only very few details of its geometry. It can also be used for computing the visible portions of a model as it forms the boundary between the visible front-facing and the hidden back-facing polygons. Silhouettes are also useful in shadow generation [Cro77], model simplification [LE97], collision detection [BV95], image registration [LSB95], and several other applications. The video presents an incremental algorithm for computing silhouettes of polyhedral models and updating them as the viewpoint changes. Most applications of interest exhibit coherence in silhouettes between successive computations as viewpoints change slowly. Our algorithm exploits this coherence to obtain fast updates of the silhouettes. Assume that we know the silhouette of a model from .a given view point. An edge ceases to be (resp., becomes) a silhouette edge if and only if it is shared by one front-facing and one back-facing polygon (resp., two polygons of the same facing), and exactly one of its adjacent polygons changes orientation. Thus, when the viewpoint is changed we are interested in finding such orientation-change events. We reduce this problem to a point-location query in a planar-map data structure.
1645664
Improved Combinatorial Group Testing for Real-World Problem Sizes
We study practically efficient methods for performing combinatorial group testing. We present efficient non-adaptive and two-stage combinatorial group testing algorithms, which identify the at most d items out of a given set of n items that are defective, using fewer tests for all practical set sizes. For example, our two-stage algorithm matches the information theoretic lower bound for the number of tests in a combinatorial group testing regimen.
43822433
Contour interpolation by straight skeletons
In this paper we present an efficient method for interpolating a piecewise-linear surface between two parallel slices, each consisting of an arbitrary number of (possibly nested) polygons that define 'material' and 'non-material' regions. This problem has applications to medical imaging, geographic information systems, etc. Our method is fully automatic and is guaranteed to produce non-self-intersecting surfaces in all cases regardless of the number of contours in each slice, their complexity and geometry, and the depth of their hierarchy of nesting. The method is based on computing cells in the overlay of the slices that form the symmetric difference between them. Then, the straight skeletons of the selected cells guide the triangulation of each face of the skeletons. Finally, the resulting triangles are lifted up in space to form an interpolating surface. We provide some experimental results on various complex examples to show the good and robust performance of our algorithm.
19387966
GeomNet: Geometric Computing Over the Internet
Geometric computing has become a central building block in fields like computer graphics, artificial intelligence, CAD and GIS databases. The paper discusses the GeomNet system. GeomNet's layered client-server architecture lets users perform distributed geometric computing over the Internet without having to download, install, and interface with application-specific software.