An official website of the United States government
Robotic manipulation problems are inherently continuous, but typically have underlying discrete structure, e.g., whether or not an object is grasped. This means many problems are multi-modal and in particular have a continuous infinity of modes. For example, in a pick-and-place manipulation domain, every grasp and placement of an object is a mode. Usually manipulation problems require the robot to transition into different modes, e.g., going from a mode with an object placed to another mode with the object grasped. To successfully find a manipulation plan, a planner must find a sequence of valid single-mode motions as well as valid transitions between these modes. Many manipulation planners have been proposed to solve tasks with multi-modal structure. However, these methods require mode-specific planners and fail to scale to very cluttered environments or to tasks that require long sequences of transitions. This paper presents a general layered planning approach to multi-modal planning that uses a discrete “lead” to bias search towards useful mode transitions. The difficulty of achieving specific mode transitions is captured online and used to bias search towards more promising sequences of modes. We demonstrate our planner on complex scenes and show that significant performance improvements are tied to both our discrete “lead” and our continuous representation.
more »
« less
This content will become publicly available on September 10, 2026
Occasionally Observed Piecewise-Deterministic Markov Processes
Not AvailablePiecewise-Deterministic Markov processes (PDMPs) are often used to model abrupt changes in the global environment or capabilities of a controlled system. This is typically done by considering a set of “operating modes” (each with its own system dynamics and performance metrics) and assuming that the mode can switch stochastically, while the system state evolves. Such models have a broad range of applications in engineering, economics, manufacturing, robotics, and biological sciences. Here, we introduce and analyze an “occasionally observed” version of mode-switching PDMPs. We show how such systems can be controlled optimally if the planner is not alerted to mode switches as they occur but may instead have access to infrequent mode observations. We first develop a general framework for handling this through dynamic programming on a higher dimensional mode-belief space. While quite general, this method is rarely practical due to the curse of dimensionality. We then discuss assumptions that allow for solving the same problem much more efficiently,with the computational costs growing linearly (rather than exponentially) with the number of modes. We use this approach to derive Hamilton-Jacobi-Bellman (HJB) PDEs and quasi-variational inequalities encoding the optimal behavior for a variety of planning horizons (fixed, infinite, indefinite, and random) and mode-observation schemes (at fixed times or on demand). We discuss the computational challenges associated with each version and illustrate the resulting methods on test problems from surveillance-evading path planning. We also include an example based on robotic navigation: a Mars rover that minimizes the expected time to target while accounting for the possibility of unobserved/incremental damages and dynamics-altering breakdowns.
more »
« less
- PAR ID:
- 10655851
- Publisher / Repository:
- Springer Nature
- Date Published:
- Journal Name:
- Communications on Applied Mathematics and Computation
- ISSN:
- 2096-6385
- Subject(s) / Keyword(s):
- Piecewise-deterministic & switching processes, Partial observability, Stochastic optimal control, Hamilton-Jacobi-Bellman (HJB) PDEs, Path planning Mathematics Subject Classification: 49K45, 49L20, 60G35, 49M25, 60J25
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this paper, we study the “decoding” problem for discrete-time, stochastic hybrid systems with linear dynamics in each mode. Given an output trace of the system, the decoding problem seeks to construct a sequence of modes and states that yield a trace “as close as possible” to the original output trace. The decoding problem generalizes the state estimation problem, and is applicable to hybrid systems with non-determinism. The decoding problem is NP-complete, and can be reduced to solving a mixed-integer linear program (MILP). In this paper, we decompose the decoding problem into two parts: (a) finding a sequence of discrete modes and transitions; and (b) finding corresponding continuous states for the mode/transition sequence. In particular, once a sequence of modes/transitions is fixed, the problem of “filling in” the continuous states is performed by a linear programming problem. In order to support the decomposition, we “cover” the set of all possible mode/transition sequences by a finite subset. We use well-known probabilistic arguments to justify a choice of cover with high confidence and design randomized algorithms for finding such covers. Our approach is demonstrated on a series of benchmarks, wherein we observe that relatively tiny fraction of the possible mode/transition sequences can be used as a cover. Furthermore, we show that the resulting linear programs can be solved rapidly by exploiting the tree structure of the set cover.more » « less
-
In 1950, Nash proposed a natural equilibrium solution concept for games hence called Nash equilibrium, and proved that all finite games have at least one. The proof is through a simple yet ingenious application of Brouwer’s (or, in another version Kakutani’s) fixed point theorem, the most sophisticated result in his era’s topology—in fact, recent algorithmic work has established that Nash equilibria are computationally equivalent to fixed points. In this paper, we propose a new class of universal non-equilibrium solution concepts arising from an important theorem in the topology of dynamical systems that was unavailable to Nash. This approach starts with both a game and a learning dynamics, defined over mixed strategies. The Nash equilibria are fixpoints of the dynamics, but the system behavior is captured by an object far more general than the Nash equilibrium that is known in dynamical systems theory as chain recurrent set. Informally, once we focus on this solution concept—this notion of “the outcome of the game”—every game behaves like a potential game with the dynamics converging to these states. In other words, unlike Nash equilibria, this solution concept is algorithmic in the sense that it has a constructive proof of existence. We characterize this solution for simple benchmark games under replicator dynamics, arguably the best known evolutionary dynamics in game theory. For (weighted) potential games, the new concept coincides with the fixpoints/equilibria of the dynamics. However, in (variants of) zero-sum games with fully mixed (i.e., interior) Nash equilibria, it covers the whole state space, as the dynamics satisfy specific information theoretic constants of motion. We discuss numerous novel computational, as well as structural, combinatorial questions raised by this chain recurrence conception of games.more » « less
-
Abstract Advancements in quantum system lifetimes and control have enabled the creation of increasingly complex quantum states, such as those on multiple bosonic cavity modes. When characterizing these states, traditional tomography scales exponentially with the number of modes in both computational and experimental measurement requirement, which becomes prohibitive as the system size increases. Here, we implement a state reconstruction method whose sampling requirement instead scales polynomially with system size, and thus mode number, for states that can be represented within such a polynomial subspace. We demonstrate this improved scaling with Wigner tomography of multimode entangled W states of up to 4 modes on a 3D circuit quantum electrodynamics (cQED) system. This approach performs similarly in efficiency to existing matrix inversion methods for 2 modes, and demonstrates a noticeable improvement for 3 and 4 modes, with even greater theoretical gains at higher mode numbers.more » « less
-
Fluorescence-encoded infrared (FEIR) spectroscopy is a recently developed technique for solution-phase vibrational spectroscopy with detection sensitivity at the single-molecule level. While its spectroscopic information content and important criteria for its practical experimental optimization have been identified, a general understanding of the electronic and nuclear properties required for highly sensitive detection, i.e., what makes a molecule a “good FEIR chromophore,” is lacking. This work explores the molecular factors that determine FEIR vibrational activity and assesses computational approaches for its prediction. We employ density functional theory (DFT) and its time-dependent version (TD-DFT) to compute vibrational and electronic transition dipole moments, their relative orientation, and the Franck–Condon factors involved in FEIR activity. We apply these methods to compute the FEIR activities of normal modes of chromophores from the coumarin family and compare these predictions with experimental FEIR cross sections. We discuss the extent to which we can use computational models to predict the FEIR activity of individual vibrations in a candidate molecule. The results discussed in this work provide the groundwork for computational strategies for choosing FEIR vibrational probes or informing the structure of designer chromophores for single-molecule spectroscopic applications.more » « less
