Mahmoud El Chamie

Masahiro Ono, Mahmoud El Chamie, Marco Pavone et al.

Choosing control inputs randomly can result in a reduced expected cost in optimal control problems with stochastic constraints, such as stochastic model predictive control (SMPC). We consider a controller with initial randomization, meaning that the controller randomly chooses from K+1 control sequences at the beginning (called K-randimization).It is known that, for a finite-state, finite-action Markov Decision Process (MDP) with K constraints, K-randimization is sufficient to achieve the minimum cost. We found that the same result holds for stochastic optimal control problems with continuous state and action spaces.Furthermore, we show the randomization of control input can result in reduced cost when the optimization problem is nonconvex, and the cost reduction is equal to the duality gap. We then provide the necessary and sufficient conditions for the optimality of a randomized solution, and develop an efficient solution method based on dual optimization. Furthermore, in a special case with K=1 such as a joint chance-constrained problem, the dual optimization can be solved even more efficiently by root finding. Finally, we test the theories and demonstrate the solution method on multiple practical problems ranging from path planning to the planning of entry, descent, and landing (EDL) for future Mars missions.

Mahmoud El Chamie, Behcet Acikmese

Markov Decision Processes (MDPs) have been used to formulate many decision-making problems in science and engineering. The objective is to synthesize the best decision (action selection) policies to maximize expected rewards (minimize costs) in a given stochastic dynamical environment. In many practical scenarios (multi-agent systems, telecommunication, queuing, etc.), the decision-making problem can have state constraints that must be satisfied, which leads to Constrained MDP (CMDP) problems. In the presence of such state constraints, the optimal policies can be very hard to characterize. This paper introduces a new approach for finding non-stationary randomized policies for finite-horizon CMDPs. An efficient algorithm based on Linear Programming (LP) and duality theory is proposed, which gives the convex set of feasible policies and ensures that the expected total reward is above a computable lower-bound. The resulting decision policy is a randomized policy, which is the projection of the unconstrained deterministic MDP policy on this convex set. To the best of our knowledge, this is the first result in state constrained MDPs to give an efficient algorithm for generating finite horizon randomized policies for CMDP with optimality guarantees. A simulation example of a swarm of autonomous agents running MDPs is also presented to demonstrate the proposed CMDP solution algorithm.

Mahmoud El Chamie, Behcet Acikmese

Markov Decision Processes (MDPs) have been used to formulate many decision-making problems in science and engineering. The objective is to synthesize the best decision (action selection) policies to maximize expected rewards (or minimize costs) in a given stochastic dynamical environment. In this paper, we extend this model by incorporating additional information that the transitions due to actions can be sequentially observed. The proposed model benefits from this information and produces policies with better performance than those of standard MDPs. The paper also presents an efficient offline linear programming based algorithm to synthesize optimal policies for the extended model.