1846400
Common metrics for human-robot interaction
This paper describes an effort to identify common metrics for task-oriented human-robot interaction (HRI). We begin by discussing the need for a toolkit of HRI metrics. We then describe the framework of our work and identify important biasing factors that must be taken into consideration. Finally, we present suggested common metrics for standardization and a case study. Preparation of a larger, more detailed toolkit is in progress.
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.
29722627
A theory of satisficing decisions and control
The existence of an optimal control policy and the techniques for finding it are grounded fundamentally in a global perspective. These techniques can be of limited value when the global behaviour of the system is difficult to characterize, as it may be when the system is nonlinear, when the input is constrained, or when only partial information is available regarding system dynamics or the environment. Satisficing control theory is an alternative approach that is compatible with the limited rationality associated with such systems. This theory is extended by the introduction of the notion of strong satisficing to provide a systematic procedure for the design of satisficing controls. The power of the satisficing approach is illustrated by applications to representative control problems.
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.
44773632
Satisficing Games
Optimization is a mathematical sophistication of the common sense view that decision makers ought to do the best they can, and leads to well known solution concepts for mathematical games. For multi-agent systems in naturalistic settings, however, uncertainty and complexity may subordinate optimal performance to the more moderate goals of functionality and robustness. Moderation is another common sense idea that can be made mathematically precise by defining a notion of comparative rationality, leading to a theory of satisficing games. Preferences in an m-agent satisficing game are characterized by a 2m-dimensional interdependence function, from which the joint m-dimensional gains and losses of the agent system can be derived and compared to determine the set of jointly satisficing decisions. This paradigm permits decision makers in the presence of uncertainty to consider multiple sets of possible actions and make decisions that are both robust and functional. Two well-known games, Prisoner's Dilemma and Battle of the Sexes, are analyzed from this, point of view.
451273
Comparing the usefulness of video and map information in navigation tasks
One of the fundamental aspects of robot teleoperation is the ability to successfully navigate a robot through an environment. We define successful navigation to mean that the robot minimizes collisions and arrives at the destination in a timely manner. Often video and map information is presented to a robot operator to aid in navigation tasks. This paper addresses the usefulness of map and video information in a navigation task by comparing a side-by-side (2D) representation and an integrated (3D) representation in both a simulated and a real world study. The results suggest that sometimes video is more helpful than a map and other times a map is more helpful than video. From a design perspective, an integrated representation seems to help navigation more than placing map and video side-by-side.
40877328
Three-Dimensional Layers of Maxima
We present an O(n log n)-time algorithm to solve the three-dimensional layers-of-maxima problem, an improvement over the prior O(n log n log log n)-time solution. A previous claimed O(n log n)-time solution due to Atallah, Goodrich, and Ramaiyer [SCG'94] has technical flaws. Our algorithm is based on a common framework underlying previous work, but to implement it we devise a new data structure to solve a special case of dynamic planar point location in a staircase subdivision. Our data structure itself relies on a new extension to dynamic fractional cascading that allows vertices of high degree in the control graph.
2560451
Teaching data structure design patterns
In this paper we present an approach for teaching the Freshman-Sophomore introduction to data structures course (CS2) in a way that provides an introduction to object-oriented software engineering patterns in addition to the theory of data structures. We survey in this paper several design patterns and describe how they can be naturally integrated in the CS2 curriculum.
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.
14677263
Teaching the analysis of algorithms with visual proofs
We describe an approach for visually teaching important proofs in the Junior-Senior level course on the design and analysis of data structures and algorithms (CS7/DS&amp;A). The main idea of this educational paradigm is to justify important claims about data structures and algorithms by using pictures that visualize proofs so clearly that the pictures can qualify as proofs themselves. The advantage of using this approach for DS&amp;A is that it augments or even replaces inductive arguments that many students find difficult. Moreover, this paradigm communicates important algorithmic facts in a compelling way for students who are more visually-oriented. We illustrate this technique by giving examples of visual proofs of several key concepts in DS&amp;A.
30272544
Characterization and Recognition of Point-Halfspace and Related Orders
We characterize four classes of geometric membership and containment orders-structurally and in terms of forbidden subposets-and present linear- or near linear-time recognition algorithms for each class. We also show that recognizing point-halfspace orders in ℝ2 is NP-hard for d≥2.