Institute for Systems Research Technical Reports

An important feature of the facility we describe is that it uses severaltypes of sensing modalities including position sensing, tactile sensingand more conventional vision sensing. It can interact with objectsof different complexity and is subject to communication constraints arising in a completelynatural and generic way. In constructing it we have used off-the-shelfcomponents wherever possible and made choices with an eye towardflexibility and reliability.

To accomplish this an interface was designed via the DELPHI programminglanguage that can take inputs from a user as well as factory details froman Excel spreadsheet, run simulations, determine an optimal toolconfiguration, and output this data as easily as possible to the user.

The Interface will guide the Simulation as many times as needed to performits gradient analysis. After the program is complete, it determines a bestcase tool configuration that meets the user's throughput while maintainingto his budget. The interface will output how many of each tool to purchaseas well the best possible tool allocation (usage) for each tool.

Existing theory is expanded intwo directions: the semi-Markov case is considered, and non-irreduciblechains are considered. In particular, the analysis of the non-irreduciblecase is a significant addition to the literature, since many real-worldsystems do not exhibit irreducibility under all stationary Markov policies. Extension of existing results to the semi-Markovcase is significant because it requires the definition of a newdynamic programming equation and a technically challenging adaptation of the Perron-Frobeniuseigenvalue from the discrete time case.

In order to determine an optimal policy, new concepts in the classificationof Markov chains need to be introduced. This is because in thenon-irreducible case, the average risk sensitive cost objective function permits extremely unlikely events to exert a controlling influence on costs. We define equivalence classes of statescalled `strongly communicating classes' and formulate in terms of thema new characterization of the underlying structureof Markov Decision Problems and Markov chains.

In the risk sensitive case, the expected cost incurred prior to a stopping time with finite expected valuecan be infinite. For this reason, we introduce an assumption: reachability with finite cost. This is the fundamental assumptionrequired to achieve the major results of this thesis.

We explore existence conditions for an optimal policy, optimality equations,and behavior for large and small risk sensitivity parameter. (Onlynon-negative risk parameters are discussed in this thesis -- i.e. the risk averse and risk neutral cases, not the risk seeking case.) Ramificationsfor the risk neutral objective function are also analyzed.Furthermore, a simple solution technique we call `recursive computation'to find an optimal policy that isapplicable to small state spaces is described through examples.

The countable state space case is explored, and results that hold only for a finite state space are also presented. Other, relatedobjective functions such as sample path cost are analyzed and discussed.

We also explore finite time horizon semi-Markov problems, and present a general technique for solving them.We define a new objective function, the minimization of which is calledthe `deadline problem'. This is a problem in which the probability of reaching the goal state in a set period of time is maximized. We transform thedeadline problem objective function into an equivalent finite-horizonrisk sensitive objective function.

In this paper, RtR control methods are generalized. The set-valued RtR controllers with ellipsoidapproximation are compared with other RtR controllers bysimulation according to the following criteria: A good RtR controller should be able to compensate for variousdisturbances, such as process drifts, process shifts (step disturbance)and model errors; moreover, it should beable to deal with limitations, bounds, cost requirement, multipletargets and time delays that are often encountered in realprocesses.

Preliminary results show the good performance of the set-valued RtRcontroller. Furthermore, this paper shows that it is insufficient to uselinear models to approximate nonlinear processes and it is necessary to developnonlinear model based RtR controllers.

Numericalexperiments on a queueing model with high-dimensional parameter vectorsdemonstrate orders of magnitude faster convergence using thesealgorithms over related $(N+1)$-Simulation finite difference analoguesand another two-simulation finite difference algorithm that updates incycles.