Here is a list of my papers:
Abstract: In this paper we address the problem of computing the permanent of (0,1)-circulant matrices. We investigate structural properties of circulant matrices, showing that, (i) if they are dense enough, then they contain large arbitrary submatrices, and, (ii) if they are very sparse, then they are not `too far' from convertible matrices. Building upon (ii), we then develop an efficient algorithm which allows us to compute permanents of very sparse circulants of size up to 200.
gzipped PostScript (115K) | PDF (301K)
Abstract: This paper contains an analysis of the permanents of the most sparse Toeplitz matrices for which the problem is already non trivial. These matrices include some examples of circulants for which none of the previous approaches could be successfully employed. For instance, we find efficient algorithms for the computation of the permanent of certain (0,1)-circulants with three nonzero entries per row, and, in some cases, we determine the explicit expression for their permanent. These results are obtained by taking advantage of the fact that these matrices have submatrices with very special properties.
gzipped PostScript (149K) | PDF (294K)
Abstract: In this paper we examine the role of very simple and noisy sensors for the tracking problem. We propose a binary sensor model, where each sensor's value is converted reliably to one bit of information only: the object is moving toward the sensor or away from the sensor. We show that a network of binary sensors has geometric properties that can be used to develop a solution for tracking with binary sensors and present resulting algorithms and simulation experiments. We develop two classes of algorithms: one that assumes the sensors have no range limits and another that limits the sensor range. Our extensive simulations show low error that decreases with sensor density.
gzipped Postscript (244K) | PDF (502K)
Abstract: In this paper we investigate problems of target surveillance with the aim of building a general framework for the evaluation of the performance of a system of autonomous agents. To this purpose we propose a class of semi-distributed stochastic navigation algorithms, that drive swarms of autonomous scouts to the surveillance of grounded targets, and we provide a novel approach to performance estimation based on analysing sequential observations of the system's state with information theoretical techniques. Our goal is to achieve a deeper understanding of the interrelations between randomness, resource consumption and ergodicity of a decentralized control system in which the decision--making process is stochastic.
gzipped Postscript (83K) | PDF (217K)
Abstract: In this paper we investigate a problem arising in decentralized registration of sensors. The application we consider involves a heterogeneous collection of sensors - some sensors have on-board Global Positioning System (GPS) capabilities while others do not. All sensors have wireless communications capability but the wirele ss communication has limited effective range. Sensors can communicate only with other sensors that are within a fixed distance of each other. Sensors with GPS capability are self-registering. Sensors without GPS capability are less expensive and smaller but they must compute estimates of their location using estimates of the distances between themselves and other sensors within their radio range. GPS-less sensors may be several radio hops away from GPS-capable sensors so registration must be inferred transitively. Our approach to solving this registration problem involves minimizing a global potential or penalty function by using only local information, determined by the radio range, available to each sensor. The algorithm we derive is a special case of a more general methodology we have developed called "Emergence Engineering".
gzipped Postscript (66K) | PDF (125K)
Abstract: Many surveillance and sensing applications involve the detection of dynamic processes. Examples include battlefield situation awareness (where the processes are vehicles and troop movements), computer and network security (where the processes are worms and other types of attacks), and homeland security (where processes are terrorist financing, planning, recruiting and attack execution activities). A Process Query System is a novel and powerful software front-end to a database or real-time sensing infrastructure that allows users to define processes at a high level of abstraction and submit process definitions as queries. We describe a current working implementation that has been used for vehicle tracking using an acoustic sensor network and for computer worm detection.
gzipped PostScript (70K) | PDF (184K)
Abstract: This paper describes a distributed algorithm for coordinating the flow of a mass of vehicles approaching a highway exit or a tollbooth. We provide the problem formulation, a general methodology for distributed control and an instantiation of this methodology to the coordinated flow problem. We analyze our algorithm and provide experimental data.
gzipped Postscript (70K) | PDF (202K)
Abstract:The Lovász theta function of a graph attracts a lot of interests due to its relation to communications issues, as well as to some central combinatorial optimization problems. A remarkable property of this function is that it is computable in polynomial time, despite being "sandwitched" between two hard to compute integers, i.e., clique and chromatic number. Very little is known about the explicit value of the theta function for special classes of graphs. In this paper we undertake the investigation of the value of the Lovász function for some special classes of sparse circulant graphs. More precisely, we provide the explicit formula for the Lovász function of the union of two cycles in two special cases, and an efficient linear time algorithm, for the general case. Indeed our algorithm takes time proportional to j, where j is the displacement between the two cycles.
no online copy available
Abstract: The theta function of a graph, also known as the Lovász number, has the remarkable property of being computable in polynomial time, despite being "sandwiched" between two hard to compute integers, i.e., clique and chromatic number. Very little is known about the explicit value of the theta function for special classes of graphs. In this paper we provide the explicit formula for the Lovász number of the union of two cycles, in two special cases, and a practically efficient algorithm, for the general case.
gzipped PostScript (109K) | PDF (231K)
Abstract: We take advantage of the special structure of computations in Z_2 to develop algorithms for the computation of Groebner bases and of the Hilbert function in the Boolean setting. Natural sources of applications for our algorithms are the counting problems. We focus, as a case study, on the computation of the permanent. To this regard, one good feature of the Groebner approach is that, unlike other general methods for the exact computation of the permanent, it is intrinsically sensitive to the structure of the specific input, and this makes it possible to use it in order to recognize and solve efficiently several easy instances.
gzipped PostScript (493K) | PDF (323K)
Abstract: OBJSA Nets are a specification language for distributed systems. Specifically they are a class of algebraic high level Petri Nets which combine Superposed Automata (SA) nets, a modular class of Petri nets, and the algebraic specification language for Adts', OBJ. This paper faces the problem of defining a formal semantics for this specification language embedding the specification into the Concurrent Rewriting Logic, introduced by J. Meseguer as a unifying model for concurrency. We showed that this logic, based upon category theory, is powerful enough to provide a formal system that captures the concurrency both at the level of parallel transition firing (control level) and at the level of the parallel computation of the data involved during each transition firing (data level).
No online copy available.
gzipped PostScript (352K) | PDF (1.2M)
Here is a list of white papers related to the Agent-Based Systems Engineering Project.
Abstract: This report summarizes our preliminary efforts at applying the methodology and techniques of agent-based systems engineering (ABSE) to the problem of designing and operating Intelligent Roads and Vehicles Systems (IRVS). First, we briefly summarize the key elements of both agent-based systems engineering and IRVS. We then show how the taxonomy of ABSE applies to the IRVS concept and how some performance metrics can be introduced. The report concludes with plans for continued work in this direction.
gzipped Postscript (56K) | PDF (145K)
Abstract: We consider control problems that arise in the context of the IRVS. Specifically, we study the dynamics of systems of fully autonomous agents that are expected to optimize a global potential function of which they have only partial knowledge. Our ultimate goal is to characterize mathematically the global performance of agent-based systems in which the inter-agent cooperation is based on local exchange of information. First we introduce what we call the Opera Problem, a natural abstraction of a class of motion problems arising commonly in systems of autonomous vehicles. We then provide a centralized solution based on traditional control theory techniques. Finally, we present and analyze a decentralized solution.
gzipped Postscript (57K) | PDF (155K)
Last Modified: Sep 4, 2008