In this paper, we perform a joint design of goal legibility and recognition in a cooperative, multi-agent pathfinding setting with partial observability. More specifically, we consider a set of identical agents (the actors) that move in an environment only partially observable to an observer in the loop. The actors are tasked with reaching a set of locations that need to be serviced in a timely fashion. The observer monitors the actors' behavior from a distance and needs to identify each actor's destination based on the actor's observable movements. Our approach generates legible paths for the actors; namely, it constructs one path from the origin to each destination so that these paths overlap as little as possible while satisfying budget constraints. It also equips the observer with a goal-recognition mapping between unique sequences of observations and destinations, ensuring that the observer can infer an actor's destination by making the minimum number of observations (legibility delay). Our method substantially extends previous work, which is limited to an observer with full observability, showing that optimizing pathfinding for goal legibility and recognition can be performed via a reformulation into a classical minimum cost flow problem in the partially observable case when the algorithms for the fully observable case are appropriately modified. Our empirical evaluation shows that our techniques are as effective in partially observable settings as in fully observable ones.

Several real-world problems in engineering and applied science require the selection of sequences that maximize a given reward function. Optimizing over sequences as opposed to sets requires exploring an exponentially larger search space and can become prohibitive in most cases of practical interest. However, if the objective function is submodular (intuitively, it exhibits a diminishing return property), the optimization problem becomes more manageable. Recently, there has been increasing interest in sequence submodularity in connection with applications such as recommender systems and online ad allocation. However, mostly ad hoc models and solutions have emerged within these applicative contexts. In consequence, the field appears fragmented and lacks coherence. In this paper, we offer a unified view of sequence submodularity and provide a generalized greedy algorithm that enjoys strong theoretical guarantees. We show how our approach naturally captures several application domains, and our algorithm encompasses existing methods, improving over them.

In this paper, we present a set of strategies to underpin the behavior of an agent that wants to arrive as close as possible to its destination without revealing it to an observer, which monitors its progress in the environment. This problem is an instance of goal obfuscation (GO), which has lately received significant attention in the AI community. With different variants of GO being proposed, the field lacks coherence and characterization from first principles. In addition, existing techniques are not robust to possible attempts of the observer to learn the agent's strategy. To fill this gap, we provide here a foundational study of GO and offer robust techniques to ensure that the agent can protect its privacy as much as possible regardless of the observer's behavior. We cast GO as an optimization problem, offer a complete theoretical analysis of it and introduce efficient algorithms to find exact solutions.

Abstract We present a technique for automatically extracting mutual exclusion invariants from temporal planning instances. It first identifies a set of invariant templates by inspecting the lifted representation of the domain and then checks these templates against properties that assure invariance. Our technique builds on other approaches to invariant synthesis presented in the literature but departs from their limited focus on instantaneous actions by addressing temporal domains. To deal with time, we formulate invariance conditions that account for the entire temporal structure of the actions and the possible concurrent interactions between them. As a result, we construct a more comprehensive technique than previous methods, which is able to find not only invariants for temporal domains but also a broader set of invariants for sequential domains. Our experimental results provide evidence that our domain analysis is effective at identifying a more extensive set of invariants, which results in the generation of fewer multi-valued state variables. We show that, in turn, this reduction in the number of variables reflects positively on the performance of the temporal planners that use a variable/value representation.

In this paper, exact formul\ae of the input-output weight distribution function and its exponential growth rate are derived for truncated convolutional encoders. In particular, these weight distribution functions are expressed in terms of generating functions of error events associated with a minimal realization of the encoder. Although explicit analytic expressions can be computed for relatively small truncation lengths, the explicit expressions become prohibitively complex to compute as the truncation lengths and the weights increase. Fortunately, a very accurate asymptotic expansion can be derived using the multidimensional saddle-point method (MSP method). This approximation is substantially easier to evaluate and is used to obtain an expression of the asymptotic spectral function, and to prove continuity and concavity in its domain (convex and closed). Finally, this approach is able to guarantee that the sequence of exponential growth rates converges uniformly to the asymptotic limit, and to estimate the speed of this convergence.

Minimum distances and maximum likelihood error probabilities of serial turbo codes with uniform interleaver are analyzed. It is shown that, for a fraction of interleavers approaching one as the block-length grows large, the minimum distance of serial turbo codes grows as a positive power of their block-length, while their error probability decreases exponentially fast in some positive power of their block-length, on sufficiently good memoryless channels. Such a typical code behavior contrasts the performance of the average serial turbo code, whose error probability is dominated by an asymptotically negligible fraction of poorly performing interleavers, and decays only as a negative power of the block-length. The analysis proposed in this paper relies on precise bounds of the minimum distance of the typical serial turbo code, whose scaling law is shown to depend both on the free distance of its outer constituent encoder, which determines the exponent of its sub-linear growth in the block-length, and on the effective free distance of its inner constituent encoder. The latter is defined as the smallest weight of codewords obtained when the input word of the inner encoder has weight two, and appears as a linear scaling factor for the minimum distance of the typical serial turbo code. Hence, despite the lack of concentration of the maximum likelihood error probability around its expected value, the main design parameters suggested by the average-code analysis turn out to characterize also the performance of the typical serial turbo code. By showing for the first time that the typical serial turbo code's minimum distance scales linearly in the effective free distance of the inner constituent encoder, the presented results generalize, and improve upon, the probabilistic bounds of Kahale and Urbanke, as well as the deterministic upper bound of Bazzi, Mahdian, and Spielman, where only the dependence on the outer encoder's free distance was proved.

In this paper we derive exact formulae of the input-output weight enumerators for truncated convolutional encoders. Although explicit analytic expressions can be computed for relatively small code lengths, they become prohibitively complex to calculate as the truncation length increases. By applying Hayman-like techniques, we present an accurate and easy to compute approximation of the weight enumerators. One of our main results is the proof that the sequence of their exponential growths converges uniformly to the asymptotic growth rate. Finally, we estimate the speed of this convergence.

The capacity of finite Abelian group codes over symmetric memoryless channels is determined. For certain important examples, such as m -PSK constellations over additive white Gaussian noise (AWGN) channels, with m a prime power, it is shown that this capacity coincides with the Shannon capacity; i.e., there is no loss in capacity using group codes. (This had previously been known for binary-linear codes used over binary-input output-symmetric memoryless channels.) On the other hand, a counterexample involving a three-dimensional geometrically uniform constellation is presented in which the use of Abelian group codes leads to a loss in capacity. The error exponent of the average group code is determined, and it is shown to be bounded away from the random-coding error exponent, at low rates, for finite Abelian groups not admitting Galois field structure.

In this paper, the ensembles of repeat multiple- accumulate codes (RAm), which are obtained by interconnecting a repeater with a cascade of m accumulate codes through uniform random interleavers, are analyzed. It is proved that the average spectral shapes of these code ensembles are equal to 0 below a threshold distance epsivmand, moreover, they form a nonincreasing sequence in m converging uniformly to the maximum between the average spectral shape of the linear random ensemble and 0. Consequently the sequence epsivmconverges to the Gilbert-Varshamov (GV) distance. A further analysis allows to conclude that if m ges 2 the RAmare asymptotically good and that epsivmis the typical normalized minimum distance when the interleaver length goes to infinity. Combining the two results it is possible to conclude that the typical distance of the ensembles RAmconverges to the Gilbert-Varshamov bound.

A class of serial turbo codes admitting low-density parity-check (LDPC) representation is considered. Their parity matrix has a random and a structured part. Thanks to their turbo structure, these codes are linear-time encodable, while they can be decoded as LDPC codes. Previous works enlightened the role of the inner encoder in the error floor region and suggested the use of a non-binary iterative decoding algorithm. In this paper, a density-evolution analysis is developed giving insight into the performance of these codes in the waterfall region. The inner encoder is optimized in order to guarantee the best tradeoff between error floor and threshold.

Various randomized consensus algorithms have been proposed in the literature. In some case randomness is due to the choice of a randomized network communication protocol. In other cases, randomness is simply caused by the potential unpredictability of the environment in which the distributed consensus algorithm is implemented. Conditions ensuring the convergence of these algorithms have already been proposed in the literature. As far as the rate of convergence of such algorithms, two approaches can be proposed. One is based on a mean square analysis, while a second is based on the concept of Lyapunov exponent. In this paper, by some concentration results, we prove that the mean square convergence analysis is the right approach when the number of agents is large. Differently from the existing literature, in this paper we do not stick to average preserving algorithms. Instead, we allow to reach consensus at a point which may differ from the average of the initial states. The advantage of such algorithms is that they do not require bidirectional communication among agents and thus they apply to more general contexts. Moreover, in many important contexts it is possible to prove that the displacement from the initial average tends to zero, when the number of agents goes to infinity.

Ensembles of regular low-density parity-check codes over any finite Abelian group G are studied. The nonzero entries of the parity matrix are randomly chosen, independently and uniformly, from an arbitrary label group of automorphisms of G. Precise combinatorial results are established for the exponential growth rate of their average type-enumerating functions with respect to the code-length N. Minimum Bhattacharyya-distance properties are analyzed when such codes are employed over a memoryless G-symmetric transmission channel. In particular, minimum distances are shown to grow linearly in N with probability one, and lower bounds are provided for the typical asymptotic normalized minimum distance. Finally, some numerical results are presented, indicating that the choice of the label group strongly affects the value of the typical minimum distance.

In this paper we study serial turbo interconnections of Abelian group codes to be used on symmetric channels. Particular attention is devoted to AWGN channel with input restricted to m-PSK constellation with corresponding group structure $\mathbb{Z}_m$. We establish the exact asymptotic decay of the average symbol and word error probabilities when the interleaver length goes to infinity (interleaver gain). Moreover, we give a detailed characterization of the distance parameter characterizing the behavior for the signal-to-noise ratio going to infinity (effective free distance). Some of our results are new also in the binary context; in particular, the lower bound to the error probability decay.

In this paper, ensembles of parallel concatenated codes are studied and rigorous results on their asymptotic performance, under the assumption of maximum-likelihood (ML) decoding, are presented. In particular, it is proven that in any parallel concatenation scheme withkbranches where allkencoders are recursive and the Bhattacharyya parameter of the channel is sufficiently small, the bit-error rate (BER) and the word-error rate go to 0 exactly likeN1-kandN2-k, respectively. Different types of ensembles by changing the subgroup of permutations used to interconnect the various encoders, are considered.

The problem of the minimum Bhattacharyya distance of group codes over symmetric channels is addressed. Ensembles of Zm-linear codes are introduced and their typical minimum distance characterized in terms of the Gilbert- Varshamov distances associated to the subgroups of Zm. For the AWGN channel with 8-PSK as input it is shown that the typical Z8-linear code achieves the Gilbert-Varshamov bound.

We consider a family of codes which can be seen both as a special kind of serial turbo codes and as LDPC codes having a parity check matrix which is partly random and partly structured. These codes are linear-time encodable, thanks to the turbo structure, and can be decoded as LDPC codes. We provide an ensemble analysis for the waterfall region, on the line of classical results for serial turbo codes, and we find some design parameters.

The emerging area of control with limited data rates incorporates ideas from both control and information theory. The data rate constraint introduces quantization into the feedback loop and gives the interconnected system a two-fold nature, continuous and symbolic. In this paper, we review the results available in the literature on data-rate-limited control. For linear systems, we show how fundamental tradeoffs between the data rate and control goals, such as stability, mean entry times, and asymptotic state norms, emerge naturally. While many classical tools from both control and information theory can still be used in this context, it turns out that the deepest results necessitate a novel, integrated view of both disciplines.

In this paper we study the ML error probability of serially concatenated schemes averaged over different interleaver ensembles. We prove asymptotic results when the interleaver length goes to infinity: differently from the parallel case, the choice of the ensemble can change the decreasing speed of error probability

In this paper we study ensembles of Abelian group codes on symmetric channels. Our main example is the AWGN channel where the inputs are restricted to a GU constellation admitting Zopfmas a generating group. For codes which are Zopfm-free modules, we prove a sort of Shannon theorem which exactly characterizes which are the rates for which reliable transmission is possible. In particular we prove that for the 2r-PSK constellation, group codes over Zopf- do achieve Shannon capacity. Finally, we study the performance of low density Zopf codes and we prove average convergence rate of their word error probability

In this paper we present a theoretical analysis of serial concatenation schemes for transmission over AWGN channels employing a geometrically uniform constellation having Zopfmas a generating group. Our schemes possess a uniform error property both with respect to the word and to the symbol. This allows to prove exact convergence results on the probability of error. We then show that, as in the binary case, there is a natural concept of distance which, at the design level of the constituent encoders, should be maximized, in order to optimize performances

Convolutional codes over rings are particularly suitable for representing codes over phase-modulation signals. In order to develop a complete structural analysis of this class of codes, it is necessary to study rational matrices over rings, which constitutes the generator matrices (encoders) for such convolutional codes. Noncatastrophic, minimal, systematic, and basic generator matrices are introduced and characterized by using a canonical form for polynomial matrices over rings. Finally, some classes of convolutional codes, defined according to the generator matrix they admit, are introduced and analyzed from a system-theoretic point of view.

Given a controllable group code, it has been shown by Forney (1970, 1973), Trott, and Loeliger (1994) that it is possible to construct a canonical encoder whose state space coincides with the canonical state space of the code, that is the essential element determining the minimal trellis of the code. The construction of such an encoder is based on the concept of controllability granule. In this paper the construction of a syndrome former for an observable group code is proposed. This syndrome former exhibits analogous properties of the above mentioned canonical encoder and, in particular, its state space coincides with the canonical state space of the code. The proposed construction is based on the concept of observability granule, introduced by Forney and Trott (1993), which dualizes the concept of controllability granule. Similarly to what happens for the encoders, each observability granule produces a map and all these maps together provide the syndrome former. The main difference is that here, to achieve the right state-space dimension, the automata associated with these maps do not evolve independently from each other, but are coupled according to a triangular structure.

Polynomial algebraic techniques have always played a central role in linear systems theory and also in the theory of convolutional codes. We show how such techniques can be generalized to study systems and codes defined over Abelian groups. The systems are considered from the "behavioral" point of view as developed by Willems in the 1980s, and some of our results can be seen as extensions of Willems' results to group systems. We also address a certain number of coding-oriented questions, and we propose concrete methods based on these algebraic techniques for the synthesis of encoders, inverters, and syndrome formers for codes over finite Abelian groups.