More Like this

1. Conversion of Certain Stochastic Control Problems into Deterministic Control Problems

   McEneaney, William M; Dower, Peter M. (July 2020, 21st IFAC World Congress)

   A class of nonlinear, stochastic staticization control problems (including minimization problems with smooth, convex, coercive payoffs) driven by diffusion dynamics with constant diffusion coefficient is considered. A fundamental solution form is obtained where the same solution can be used for a limited variety of terminal costs without re-solution of the problem. One may convert this fundamental solution form from a stochastic control problem form to a deterministic control problem form. This yields an equivalence between certain second-order (in space) Hamilton-Jacobi partial differential equations (HJ PDEs) and associated first-order HJ PDEs. This reformulation has substantial numerical implications. 

   more » « less
2. Witnessability of Undecidable Problems

   https://doi.org/10.1145/3571227  

   Ding, Shuo; Zhang, Qirun (January 2023, Proceedings of the ACM on Programming Languages)

   Many problems in programming language theory and formal methods are undecidable, so they cannot be solved precisely. Practical techniques for dealing with undecidable problems are often based on decidable approximations. Undecidability implies that those approximations are always imprecise. Typically, practitioners use heuristics andad hocreasoning to identify imprecision issues and improve approximations, but there is a lack of computability-theoretic foundations about whether those efforts can succeed. This paper shows a surprising interplay between undecidability and decidable approximations: there exists a class of undecidable problems, such that it is computable to transform any decidable approximation to a witness input demonstrating its imprecision. We call those undecidable problemswitnessable problems. For example, if a program propertyPis witnessable, then there exists a computable functionf_P, such thatf_Ptakes as input the code of any program analyzer targetingPand produces an input programwon which the program analyzer is imprecise. An even more surprising fact is that the class of witnessable problems includes almost all undecidable problems in programming language theory and formal methods. Specifically, we prove the diagonal halting problemKis witnessable, and the class of witnessable problems is closed under complements and many-one reductions. In particular, all “non-trivial semantic properties of programs” mentioned in Rice’s theorem are witnessable. We also explicitly construct a problem in the non-witnessable (and undecidable) class and show that both classes have cardinality 2^ℵ₀. Our results offer a new perspective on the understanding of undecidability: for witnessable problems, although it is impossible to solve them precisely, it is always possible to improve any decidable approximation to make it closer to the precise solution. This fact formally demonstrates that research efforts on such approximations are promising and shows there exist universal ways to identify precision issues of program analyzers, program verifiers, SMT solvers, etc., because their essences are decidable approximations of witnessable problems. 

   more » « less
3. More green, fewer problems: landcover relates to perception of environmental problems

   https://doi.org/10.1002/fee.2596  

   Suchy, Amanda K; Anderson, Elsa C; Fork, Megan L; Lin, Laurence; Locke, Dexter H; Groffman, Peter M; Grove, J Morgan; LaDeau, Shannon L; Rosi, Emma J (April 2023, Frontiers in Ecology and the Environment)

   The relationship between (a) the structure and composition of the landscape around an individual's home and (b) environmental perceptions and health outcomes has been well demonstrated (eg the value of vegetation cover to well‐being). Few studies, however, have examined how multiple landscape features (eg vegetation and water cover) relate to perceptions of multiple environmental problems (eg air or water quality) and whether those relationships hold over time. We utilized a long‐term dataset of geolocated telephone surveys in Baltimore, Maryland, to identify relationships between residents’ perceptions of environmental problems and nearby landcover. Residents of neighborhoods with more vegetation or located closer to water were less likely to perceive environmental problems. Water quality was one exception to this trend, in that people were more likely to perceive water‐quality problems when nearby water cover was greater. These trends endured over time, suggesting that these relationships are stable and therefore useful for informing policy aimed at minimizing perceived environmental problems. 

   more » « less
4. Conversion of a Class of Stochastic Control Problems to Fundamental-Solution Deterministic Control Problems

   McEneaney, William M; Dower, Peter M. (July 2020, Proceedings of the American Control Conference)

   A new optimal control based representation for stationary action trajectories is constructed by exploiting connections between semiconvexity, semiconcavity, and stationarity. This new representation is used to verify a known two-point boundary value problem characterization of stationary action. 

   more » « less
5. Conversion of a Class of Stochastic Control Problems to Fundamental-Solution Deterministic Control Problems

   McEneaney, William M; Dower, Peter M. (July 2020, Proceedings of the American Control Conference)

   A class of nonlinear, stochastic staticization control problems (including minimization problems with smooth, convex, coercive payoffs) driven by diffusion dynamics and constant diffusion coefficient is considered. Using dynamic programming and tools from static duality, a fundamental solution form is obtained where the same solution can be used for a variety of terminal costs without re-solution of the problem. Further, this fundamental solution takes the form of a deterministic control problem rather than a stochastic control problem. 

   more » « less