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

Subject: search.filters.subject.dynamic programming

Search Results

Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    The MDLe Engine -- A Software Tool for Hybrid Motion Control
    (2000) Hristu, Dimitrios; Krishnaprasad, Perinkulam S.; Andersson, Sean B.; Zhang, F.; Sodre, P.; D'Anna, L.; ISR; CDCSS
    One of the important but often overlooked practical challenges in motion control for robotics and other autonomous machines has to do with the implementation of theoretical tools into software that will allow the system to interact effectively with the physical world. More often than not motion control programs are machine-specific and not reusable, even when the underlying algorithm does not require any changes.

    The work on Motion Description Languages (MDL) has been an effort to formalize a general-purpose robot programming language that allows one to incorporate both switching logic and differential equations. Extended MDL (MDLe) is a device-independent programming language for hybrid motion control, accommodating hybrid controllers, multi-robot interactions and robot-to-robot communications.

    The purpose of this paper is to describe the "MDLe engine," a software tool that implements the MDLe language.

    We have designed a basic compiler/software foundation for writing MDLe code. We provide a brief description of the MDLe syntax, implementation architecture, and functionality. Sample programs are presented together with the results of their execution on a set of physical and simulated mobile robots.

  • Thumbnail Image
    Item
    A Hierarchical Structure For Finite Horizon Dynamic Programming Problems
    (2000) Zhang, Chang; Baras, John S.; Baras, John S.; ISR; CSHCN
    In dynamic programming (Markov decision) problems, hierarchicalstructure (aggregation) is usually used to simplify computation. Most research on aggregation ofMarkov decision problems is limited to the infinite horizon case, which has good tracking ability. However, in reallife, finite horizon stochastic shortest path problems are oftenencountered.

    In this paper, we propose a hierarchical structure to solve finite horizon stochastic shortest pathproblems in parallel. In general, the approach reducesthe time complexity of the original problem to a logarithm level, which hassignificant practical meaning.

  • Thumbnail Image
    Item
    Intelligent Distributed Fault Management for Communication Networks
    (2000) Li, Hongjun; Baras, John S.; ISR; CSHCN
    In this paper, we present an intelligent, distributed fault management system for communication networks using belief networks as fault model and inference engine. The managed network is divided into domains and for each domain, there is an intelligent agent called Domain Diagnostic Agent attached to it, which is responsible for this domain's fault management. Belief network models are embedded in such an agent and under symptoms observation, the posterior probabilities of each candidate fault node being faulty is computed. We define the notion of right diagnosis, describe the diagnosis process based on this concept, and present a strategy for generation of test sequence.
  • Thumbnail Image
    Item
    Group Invariance and Symmetries in Nonlinear Control and Estimation
    (2000) Baras, John S.; ISR
    We consider nonlinear filtering problems, nonlinear robust control problems and the partial differential equations that characterize their solutions. These include the Zakai equation, and in the robust control case two coupled Dynamic Programming equations.

    We then characterize equivalence between two such problems when we can compute the solution of one from the solution of the other using change of dependent, independent variables and solving an ordinary differential equation.

    We characterize the resulting transformation groups via their Lie Algebras. We illustrate the relationship of these results to symmetries and invariances in physics, Noether's theorem, and calculus of variations.

    We show how using these techniques one can solve nonlinear problems by reduction to linear ones.

    Second Nonlinear Control Network (NCN) Workshop, June 5, 2000

  • Thumbnail Image
    Item
    A Lower Bounding Result for the Optimal Policy in an Adaptive Staffing Problem
    (1998) Assad, Arjang A.; Fu, Michael C.; Yoo, Jae-sin; ISR
    We derive a lower bound for the staffing levels required to meet a projected load in a retail service facility. We model the queueing system as a Markovian process with non-homogeneous Poisson arrivals. Motivated by an application from the postal services, we assume that the arrival rate is piecewise constant over the time horizon and retain such transient effects as build- up in the system. The optimal staffing decision is formulated as a multiperiod dynamic programming problem where staff is allocated to each time period to minimize the total costs over the horizon. The main result is the derivation of a lower bound on the staffing requirements that is computed by decoupling successive time periods.
  • Thumbnail Image
    Item
    Monotone Optimal Policies for a Transient Queueing Staffing Problem
    (1997) Fu, Michael C.; Marcus, Steven I.; Wang, I-Jeng; ISR
    We consider the problem of determining the optimal policy for staffing a queueing system over multiple periods, using a model that takes into account transient queueing effects. Formulating the problem in a dynamic programming setting, we show that the optimal policy follows a monotone optimal control by establishing the submodularity of the objective function with respect to the staffing level and initial queue size in a period. In particular, this requires proving that the system occupancy in a G/M/s queue is submodular in the number of servers and initial system occupancy.
  • Thumbnail Image
    Item
    Optimal Admission Control of Two Traffic Types at a Circuit- Switched Network Node
    (1991) Lambadaris, Ioannis E.; Narayan, P.; Viniotis, I.; ISR
    Two communication traffic streams with Poisson statistics arrive at a network node on separate routes. These streams are to be forwarded to their destinations via a common trunk. The two links leading to the common trunk have capacities C1 and C2 bandwidth units, respectively, while the capacity of the common trunk is C bandwidth units, where C < C1 + C2. Calls of either traffic type that are not admitted at the node are assumed to be discarded. An admitted call of either type will occupy, for an exponentially distributed random time, one bandwidth unit on its forwarding link as well as on the common trunk. Our objective is to determine a scheme for the optimal dynamic allocation of available bandwidth among the two traffic streams so as to minimize a weighted blocking cost. The problem is formulated as a Markov decision process. By using dynamic programming principles, the optimal admission policy is shown to be of the "bang-bang" type, characterized by appropriate "switching curves". The case of a general circuit-switched network, as well as numerical examples, are also presented.