Institute for Systems Research Technical Reports
Permanent URI for this collectionhttp://hdl.handle.net/1903/4376
This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browse
575 results
Search Results
Item Bat-Inspired Robot Navigation(2009-08) Kuhlman, Michael Joseph; McRoberts, Kate; Horiuchi, Timothy K.; Krishnaprasad, P. S.A key objective of Robotics is the autonomous navigation of mobile robots through an obstacle field. Inspired by echolocating bats, we developed a two-part navigation system consisting of obstacle detection through echolocation and motion planning. The first part relies upon a binaural sonar system, which emits ultrasonic pulses and then determines the interaural level difference (ILD) of the returning echoes to infer obstacle locations. Next, the Openspace motion planner computes the best direction of travel based on the locations of the target and the detected obstacles. We implemented this navigation system on a mobile platform, which repeatedly computes the safest direction of travel and moves accordingly, ultimately generating a real-time path to the goal.Item Digital Signal Processors: A brief summary(2008) Kotha, Aparna; Barua, RajeevItem Distributed Topology Control for Stable Path Routing in Mobile Ad Hoc Networks(2009-11-25) Somasundaram, Kiran; Jain, Kaustubh; Tabatabaee, Vahid; Baras, JohnItem Path Optimization Techniques for Trusted Routing in Mobile Ad-Hoc Networks: An Interplay Between Ordered Semirings(2008) Somasundaram, Kiran; Baras, John; Baras, JohnIn this paper, we formulate the problem of trusted routing as a transaction of services over a complex networked environment. We present definitions from service-oriented environments which unambiguously capture the difference between trust and reputation relations. We show that the trustworthiness measures associated with these relations have a linear order embedded in them. Identifying this order structure permits us to treat the trusted routing problem as a bi-objective path optimization problem. Further, we present polynomial time solutions to obtain the optimal routing paths in various biobjective settings. In developing these algorithms, we identify an interesting semiring decomposition principle that yields a distributed solutionItem Distributed Topology Control for Stable Path Routing in Mobile Ad Hoc Networks(2009-12-09) Somasundaram, Kiran K.; Jain, Kaustubh; Tabatabaee, Vahid; Baras, John S.In this paper, we introduce the stable path topology control problem for routing in Mobile Ad Hoc Networks (MANETs). We formulate the problem as a constrained multiagent optimization problem with only local neighborhood information. We develop and prove local pruning strategies that solve this problem. We also introduce the notion of distorted pruning, which offers a systematic method to trade path stability off against the hop count metric. Finally, we quantify the performance of our pruning algorithms using several simulation scenarios.Item Certifying the Optimality of a Distributed State Estimation System via Majorization Theory(2009) Lipsa, Gabriel; Martins, Nuno; Martins, NunoConsider a first order linear time-invariant discrete time system driven by process noise, a pre-processor that accepts causal measurements of the state of the system, and a state estimator. The pre-processor and the state estimator are not co-located, and, at every time-step, the pre-processor transmits either a real number or an erasure symbol to the estimator. We seek the pre-processor and the estimator that jointly minimize a cost that combines two terms; the expected squared state estimation error and a communication cost. In our formulation, the transmission of a real number from the pre-processor to the estimator incurs a positive cost while erasures induce zero cost. This paper is the first to prove analytically that a symmetric threshold policy at the pre-processor and a Kalman-like filter at the estimator, which updates its estimate linearly in the presence of erasures, are jointly optimal for our problem.Item Convergence results for the linear consensus problem under Markovian random graphs(2009) Matei, Ion; John, Baras; Baras, JohnThis note discusses the linear discrete and continuous time consensus problem for a network of dynamic agents with directed information flows and random switching topologies. The switching is determined by a Markov chain, each topology corresponding to a state of the Markov chain. We show that, under doubly stochastic assumption on the matrices involved in the linear consensus scheme, average consensus is achieved in the mean square sense and almost surely if and only if the graph resulted from the union of graphs corresponding to the states of the Markov chain is strongly connected. The aim of this note is to show how techniques from Markovian jump linear systems theory, in conjunction with results inspired by matrix and graph theory, can be used to prove convergence results for stochastic consensus problems. IItem Convergence Results for Ant Routing Algorithms via Stochastic Approximations(2009-10) Purkayastha, Punyaslok; Baras, John; Baras, JohnIn this paper, we provide convergence results for an Ant-Based Routing (ARA) Algorithm for wireline, packet-switched communication networks, that are acyclic. Such algorithms are inspired by the foraging behavior of ants in nature. We consider an ARA algorithm proposed by Bean and Costa. The algorithm has the virtues of being adaptive and distributed, and can provide a multipath routing solution. We consider a scenario where there are multiple incoming data traffic streams that are to be routed to their respective destinations via the network. Ant packets, which are nothing but probe packets, are introduced to estimate the path delays in the network. The node routing tables, which consist of routing probabilities for the outgoing links, are updated based on these delay estimates. In contrast to the available analytical studies in the literature, the link delays in our model are stochastic, time-varying, and dependent on the link traffic. The evolution of the delay estimates and the routing probabilities are described by a set of stochastic iterative equations. In doing so, we take into account the distributed and asynchronous nature of the algorithm operation. Using methods from the theory of stochastic approximations, we show that the evolution of the delay estimates can be closely tracked by a deterministic ODE (Ordinary Differential Equation) system, when the step-size of the delay estimation scheme is small. We study the equilibrium behavior of the ODE system in order to obtain the equilibrium behavior of the routing algorithm. We also explore properties of the equilibrium routing probabilities, and provide illustrative simulation results.Item On Convergence of Evolutionary Computation for Stochastic Combinatorial Optimization(2009-09) Chang, Hyeong SooExtending Rudolph's works on the convergence analysis of evolutionary computation (EC) for deterministic combinatorial optimization problems (COPs), this brief paper establishes a probability one convergence of some variants of explicit-averaging EC to an optimal solution and the optimal value for solving stochastic COPs.Item Distributed subgradient method under random communication topology - the e(2009-09) Matei, Ion; Baras, John; Baras, JohnIn this note we study the performance metrics (rate of convergence and guaranteed region of convergence) of a multi-agent subgradient method for optimizing a sum of convex functions. We assume that the agents exchange information according to a communication topology modeled as a random graph, independent of other time instances. Under a strong convexity type of assumption, we express the performance metrics directly as functions of the estimates of the optimal decision vector. We emphasize how the probability distribution of the random graph affects the upper bounds on the performance metrics. This provide a guide for tuning the parameters of the communication protocol such that good performance of the multi-agent subgradient method is ensured. We perform the tuning of the protocol parameters for two communication scenarios. In the first scenario, we assume a randomized scheme for link activation with no-error transmissions while in the second scenario we use a pre-established order of transmissions but we consider the interference effect. Both these scenarios are applied on a small world type of topology.