43673902
Coordinated target assignment and intercept for unmanned air vehicles
Presents an end-to-end solution to the battlefield scenario where M unmanned air vehicles are assigned to strike N known targets, in the presence of dynamic threats. The problem is decomposed into the subproblems of (1) cooperative target assignment, (2) coordinated UAV intercept, (3) path planning, and (4) feasible trajectory generation. The design technique is based on a hierarchical approach to coordinated control. Detailed simulation results are presented.
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.
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.
17845810
A binary-categorization approach for classifying multiple-record Web documents using application ontologies and a probabilistic model
The amount of information available on the World Wide Web has been increasing dramatically in recent years. To enhance speedy searching and retrieving Web documents of interest, researchers and practitioners have partially relied on various information retrieval techniques. We propose a probabilistic model to classify Web documents into relevant documents and irrelevant documents with respect to a particular application ontology, which is a conceptual-model snippet of standard ontologies. Our probabilistic model is based on multivariate statistical analysis and is different from the conventional probabilistic information retrieval models. The experiments we have conducted on a set of representative Web documents indicate that the proposed probabilistic model is promising in binary-categorization of multiple-record Web documents.
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.
15586236
Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings
We investigate the problem of drawing an arbitrary n-node binary tree orthogonally in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspect ratio to be chosen as being O(1) or sometimes even an arbitrary parameter. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call “subtree separation.” We investigate both upward and non-upward drawings, achieving area bounds of O(n log n) and O(n log log n), respectively, and we show that, at least in the case of upward drawings, our area bound is optimal to within constant factors.
13413744
Snap rounding line segments efficiently in two and three dimensions
We study the problem of robustly rounding a set S of n line segments in R2 using the snap rounding paradigm. In this paradigm each pixel containing an endpoint or intersection point is called “hot,” and all segments intersecting a hot pixel are re-routed to pass through its center. We show that a snap-rounded approximation to the arrangement defined by S can be built in an output-sensitive fashion, and that this can be done without first determining all the intersecting pairs of segments in S. Specifically, we give a deterministic plan~sweep algorithm running in time O(n bgn -F&H Ihl10g ~), where ~ is the set of hot pixela and \hl is the number of segments intersecting a hot pixel h E H. We also give a simple randomized incremental construction whose expected running time matches that of our deterministic algorithm. The complexity of these algorithms is optimal up to polylogarithmic factors. “This research is supported by NSF grant CCR9625289 and by U.S. ARO grsnt DAAH0496-1-O013. tThis rese~ch is supported by NSF grant CCR9623851 and US Army MUFU grant 5-23542-A. Permission 10make digil; llhd mpits tll’illl tw [ml o~lhis m:lterinl Ibr persomrl or Clossroom me is grnnled tvilllo{ll lid prnvidcrl 1}101Ihe copIcs are not mode nr distrihukd Ibr proli( or conm~L$rci.o I adwrnlngc. Ihc copy ri~l notice. Ihe tillc nl’the puhlicotion :Ind ih da(c ;Ippcilr. aml nn[iw IS given ihal cnpJTighl is h) pcrmissmn ol’lhc ,\(’il. [m. “1’0cnp) olhcn! M,. to rcpuhl ish. 10pnsl on swvers or It>rcdislrilw Ic Io Iisls. requires spwi Iic permission md~or tiec ( “ompttf{rfwndi ( ;wmcrr] 9Xii~.cl:r:m,c Copyrighl I 997 ,AChl 0M79 I-X78-997 ‘(I6,,S.75{1 LEONIDAS J. GUIBASt Dept. of Computer Science
1377517
Efficient perspective-accurate silhouette computation and applications
Silhouettes are perceptually and geometrically salient features of geo metric models. Hence a number of graphics and visualization applications need to find them to aid further processing. The efficient computation of silhouettes, especially in the context of perspective projection, is known to be difficult. This paper presents a novel efficient and practical algorithm to compute silhouettes from a sequence of viewpoints under perspective projection. Parallel projection is a special case of this algorithm. Our approach is based on a point-plane duality in three dimensions, which allows an efficient computation of the \emph{changes} in the silhouette of a polygonal model between consecutive frames. In addition, we present several applications of our technique to problems from computer graphics and medical visualization. We also provide experimental data that show the efficiency of our approach.
 million vertices on an SGI Onyx workstation.
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.
29861535
A polygonal approach to hidden-line and hidden-surface elimination
We present algorithms for the well-known hidden-line and hidden-surface elimination problems. Our algorithms are optimal in the worst case, and are also able to take advantage of problem instances that are “simpler” than in the worst case. Specifically, our algorithms run in O(n log n + k + t) time, where n is the number of edges, and k (resp. t) is the number of intersecting pairs of line segments (resp. polygons) in the projection plane π. Our algorithms are based on a polygon-based strategy, rather than an edge-based strategy, and are quite simple.