More Like this

1. Controlling 2D PDEs using mobile collocated actuators-sensors and their simultaneous guidance constrained over path-dependent reachability regions

   https://doi.org/10.23919/ACC50511.2021.9482892  

   Demetriou, Michael A. (May 2021, 021 American Control Conference (ACC))

   Employing mobile actuators and sensors for control and estimation of spatially distributed processes offers a significant advantage over immobile actuators and sensors. In addition to the control performance improvement, one also comes across the economic advantages since fewer devices, if allowed to be repositioned within a spatial domain, must be employed. While simulation studies of mobile actuators report superb controller performance, they are far from reality as the mechanical constraints of the mobile platforms carrying actuators and sensors have to satisfy motional constraints. Terrain platforms cannot behave as point masses without inertia; instead they must satisfy constraints which are adequately represented as path-dependent reachability sets. When the control algorithm commands a mobile platform to reposition itself in a different spatial location within the spatial domain, this does not occur instantaneously and for the most part the motion is not omnidirectional. This constraint is combined with a computationally feasible and suboptimal control policy with mobile actuators to arrive at a numerically viable control and guidance scheme. The feasible control decision comes from a continuous-discrete control policy whereby the mobile platform carrying the actuator is repositioned at discrete times and dwells in a specific position for a certain time interval. Moving to a subsequent spatial location and computing its associated path over a physics-imposed time interval, a set of candidate positions and paths is derived using a path-dependent reachability set. Embedded into the path-dependent reachability sets that dictate the mobile actuator repositioning, a scheme is proposed to integrate collocated sensing measurements in order to minimize costly state estimation schemes. The proposed scheme is demonstrated with a 2D PDE having two sets of collocated actuator-sensor pairs onboard mobile platforms. 

   more » « less
2. Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers

   https://doi.org/10.1145/3368826.3377916  

   Javanmard, Mohammad Mahdi; Ahmad, Zafar; Kong, Martin; Pouchet, Louis-Noël; Chowdhury, Rezaul; Harrison, Robert (February 2020, CGO 2020: Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization)

   We present a novel framework to automatically derive highly efficient parametric multi-way recursive divide-&-conquer algorithms for a class of dynamic programming (DP) problems. Standard two-way or any fixed R-way recursive divide-&-conquer algorithms may not fully exploit many-core processors. To run efficiently on a given machine, the value of R may need to be different for every level of recursion based on the number of processors available and the sizes of memory/caches at different levels of the memory hierarchy. The set of R values that work well on a given machine may not work efficiently on another machine with a different set of machine parameters. To improve portability and efficiency, Multi-way Autogen generates parametric multi-way recursive divide-&-conquer algorithms where the value of R can be changed on the fly for every level of recursion. We present experimental results demonstrating the performance and scalability of the parallel programs produced by our framework. 

   more » « less
3. Optimal algorithms for scheduling under time-of-use tariffs

   https://doi.org/10.1007/s10479-021-04059-3  

   Chen, Lin; Megow, Nicole; Rischke, Roman; Stougie, Leen; Verschae, José (September 2021, Annals of Operations Research)

   null (Ed.)

   Abstract We consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some time-dependent cost, the time-of-use tariff, which must be paid in addition to the standard scheduling cost. We focus on preemptive single-machine scheduling and two classical scheduling cost functions, the sum of (weighted) completion times and the maximum completion time, that is, the makespan. While these problems are easy to solve in the classical scheduling setting, they are considerably more complex when time-of-use tariffs must be considered. We contribute optimal polynomial-time algorithms and best possible approximation algorithms. For the problem of minimizing the total (weighted) completion time on a single machine, we present a polynomial-time algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time slots to be used for preemptively scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. For the more general problem, in which jobs may have individual weights, we develop a polynomial-time approximation scheme (PTAS) based on a dual scheduling approach introduced for scheduling on a machine of varying speed. As the weighted problem is strongly NP-hard, our PTAS is the best possible approximation we can hope for. For preemptive scheduling to minimize the makespan, we show that there is a comparably simple optimal algorithm with polynomial running time. This is true even in a certain generalized model with unrelated machines. 

   more » « less
4. Desensitized Trajectory Optimization for Hypersonic Vehicles

   https://doi.org/10.1109/AERO50100.2021.9438511  

   Makkapati, Venkata Ramana; Ridderhof, Jack; Tsiotras, Panagiotis; Hart, Joseph; van Bloemen Waanders, Bart (March 2021, IEEE Aerospace Conference)

   This paper addresses trajectory optimization for hypersonic vehicles under atmospheric and aerodynamic uncertainties using techniques from desensitized optimal control (DOC), wherein open-loop optimal controls are obtained by minimizing the sum of the standard objective function and a first-order penalty on trajectory variations due to parametric uncertainty. The proposed approach is demonstrated via numerical simulations of a minimum-final-time Earth reentry trajectory for an X-33 vehicle with an uncertain atmospheric scale height and drag coefficient. Monte Carlo simulations indicate that dispersions in the final position footprint and the final energy can be significantly reduced without closed-loop control and with little tradeoff in the performance metric set for the trajectory. 

   more » « less
5. Finding the Best Dueler

   https://doi.org/10.3390/math11071568  

   Zhang, Zhengu; Ross, Sheldon M (April 2023, Mathematics)

   Consider a set of n players. We suppose that each game involves two players, that there is some unknown player who wins each game it plays with a probability greater than 1/2, and that our objective is to determine this best player. Under the requirement that the policy employed guarantees a correct choice with a probability of at least some specified value, we look for a policy that has a relatively small expected number of games played before decision. We consider this problem both under the assumption that the best player wins each game with a probability of at least some specified value >1/2, and under a Bayesian assumption that the probability that player i wins a game against player j is its value divided by the sum of the values, where the values are the unknown values of n independent and identically distributed exponential random variables. In the former case, we propose a policy where chosen pairs play a match that ends when one of them has had a specified number of wins more than the other; in the latter case, we propose a Thompson sampling type rule. 

   more » « less