Explore the vast range of titles available.

We formulate and study a two-player duel game as a terminal payoffs stochastic game. Players 𝑃1,𝑃2 are standing in place and, in every turn, each may shoot at the other (in other words, abstention is allowed). If 𝑃𝑛 shoots 𝑃𝑚 (𝑚≠𝑛), either they hit and kill them (with probability 𝑝𝑛) or they miss and 𝑃𝑚 is unaffected (with probability 1−𝑝𝑛). The process continues until at least one player dies; if no player ever dies, the game lasts an infinite number of turns. Each player receives a positive payoff upon killing their opponent and a negative payoff upon being killed. We show that the unique stationary equilibrium is for both players to always shoot at each other. In addition, we show that the game also possesses 'cooperative' (i.e., non-shooting) non-stationary equilibria. We also discuss a certain similarity that the duel has to the iterated Prisoner's Dilemma.

We study a duel game in which each player has incomplete knowledge of the game parameters. We present a simple, heuristically motivated and easily implemented algorithm by which, in the course of repeated plays, each player estimates the missing parameters and consequently learns his optimal strategy.

A duel involves two stationary players who shoot at each other until at least one of them dies; a truel is similar but involves three players. In the past, the duel has been studied mainly as a component of the truel, which has received considerably more attention. However we believe that the duel is interesting in itself. In this paper we formulate the duel (with either simultaneous or sequential shooting) as a discounted stochastic game . We show that this game has a unique Nash equilibrium in stationary strategies ; however, it also possesses cooperation-promoting Nash equilibria in nonstationary strategies . We show that these are also subgame perfect equilibria. Finally, we argue that the nature of the game and its equilibria is similar to that of the repeated Prisoner’s dilemma .

The cops-and-robber (CR) game has been used in mobile robotics as a discretized model (played on a graph G) of pursuit/evasion problems. The “classic” CR version is a perfect information game: the cops’ (pursuer’s) location is always known to the robber (evader) and vice versa. Many variants of the classic game can be defined: the robber can be invisible and also the robber can be either adversarial (tries to avoid capture) or drunk (performs a random walk). Furthermore, the cops and robber can reside in either nodes or edges of G. Several of these variants are relevant as models or robotic pursuit/evasion. In this paper, we first define carefully several of the variants mentioned above and related quantities such as the cop number and the capture time. Then we introduce and study the cost of visibility (COV), a quantitative measure of the increase in difficulty (from the cops’ point of view) when the robber is invisible. In addition to our theoretical results, we present algorithms which can be used to compute capture times and COV of graphs which are analytically intractable. Finally, we present the results of applying these algorithms to the numerical computation of COV.

Binary diffing is a commonly used technique for detecting syntactic and semantic similarities and/or differences between two programs’ binary executables ( not source code). Here we present REveal , a binary diffing application. REveal is based on the detection of Function Call Graph (FCG) approximate isomorphism and improves both speed and accuracy, mainly by the use of two techniques. First, we propose the use of hierarchical Community Detection (CD) in executables’ FCGs, for the purpose of detecting groups of densely connected functions, thus partitioning them in smaller groups. Moreover, we use Locality-Sensitive Hashing (LSH) for further grouping of similar functions in hash buckets. Both techniques are used in a divide-and-conquer fashion to simplify the diffing process of the programs being compared, practically reducing it to diffing of their FCG communities and LSH buckets.

Most of the text categorization algorithms in the literature represent documents as collections of words. An alternative which has not been sufficiently explored is the use of word meanings, also known as senses. In this paper, using several algorithms, we compare the categorization accuracy of classifiers based on words to that of classifiers based on senses. The document collection on which this comparison takes place is a subset of the annotated Brown Corpus semantic concordance. A series of experiments indicates that the use of senses does not result in any significant categorization improvement. [PUBLICATION ABSTRACT]

We present Guaranteed Search with Spanning Trees (GSST), an anytime algorithm for multi-robot search. The problem is as follows: clear the environment of any adversarial target using the fewest number of searchers. This problem is NP-hard on arbitrary graphs but can be solved in linear-time on trees. Our algorithm generates spanning trees of a graphical representation of the environment to guide the search. At any time, spanning tree generation can be stopped yielding the best strategy so far. The resulting strategy can be modified online if additional information becomes available. Though GSST does not have performance guarantees after its first iteration, we prove that several variations will find an optimal solution given sufficient runtime. We test GSST in simulation and on a human-robot search team using a distributed implementation. GSST quickly generates clearing schedules with as few as 50% of the searchers used by competing algorithms.

We formulate and study a two-player static duel game as a nonzero-sum discounted stochastic game. Players \\(P_{1},P_{2}\\) are standing in place and, in each turn, one or both may shoot at the other player. If \\(P_{n}\\) shoots at \\(P_{m}\\) (\\(m\\neq n\\)), either he hits and kills him (with probability \\(p_{n}\\)) or he misses him and \\(P_{m}\\) is unaffected (with probability \\(1-p_{n}\\)). The process continues until at least one player dies; if nobody ever dies, the game lasts an infinite number of turns. Each player receives unit payoff for each turn in which he remains alive; no payoff is assigned to killing the opponent. We show that the the always-shooting strategy is a NE but, in addition, the game also possesses cooperative (i.e., non-shooting) Nash equilibria in both stationary and nonstationary strategies. A certain similarity to the repeated Prisoner's Dilemma is also noted and discussed.

For the offline segmentation of long hydrometeological time series, a new algorithm which combines the dynamic programming with the recently introduced remaining cost concept of branch-and-bound approach is developed. The algorithm is called modified dynamic programming (mDP) and segments the time series based on the first-order statistical moment. Experiments are performed to test the algorithm on both real world and artificial time series comprising of hundreds or even thousands of terms. The experiments show that the mDP algorithm produces accurate segmentations in much shorter time than previously proposed segmentation algorithms.

In this short note we study a class of multi-player, turn-based games with deterministic state transitions and reachability / safety objectives (this class contains as special cases \"classic\" two-player reachability and safety games as well as multi-player \"stay--in-a-set\" and \"reach-a-set\" games). Quantitative and qualitative versions of the objectives are presented and for both cases we prove the existence of a deterministic and memoryless Nash equilibrium; the proof is short and simple, using only Fink's classic result about the existence of Nash equilibria for multi-player discounted stochastic games.