All Publications

This article presents a formal specification framework for planning and control of autonomous robots, focusing on the challenge of managing complex tradeoffs among multiple potentially conflicting objectives. These include hierarchical relationships and noncomparable objectives, some of which may be too complex to be captured by standard additive cost functions. We leverage the rulebook formalism to represent such objectives and their relationships and formulate two control synthesis problems: single-strategy synthesis, which seeks one optimal strategy, and complete synthesis, which computes the full set of optimal strategies with respect to a rulebook, analogous to the Pareto front in multiobjective planning. We show that our formulation generalizes existing temporal logic-based and optimization-based planning and control, providing a unifying framework across robotics, formal methods, control theory, and operation research. For single-strategy synthesis, we identify tractable subclasses and present a polynomial-time algorithm that accommodates richer combinations of objectives than prior work. For complete synthesis, we introduce an algorithm to compute all optimal solutions and analyze its computational complexity. In both cases, we present case studies that include complex multiobjective planning problems and demonstrate the practical effectiveness of our approach compared to existing methods.

AbstractKatok’s special representation theorem states that any free ergodic measure- preserving $\mathbb {R}^{d}$Rd -flow can be realized as a special flow over a $\mathbb {Z}^{d}$Zd -action. It provides a multidimensional generalization of the ‘flow under a function’ construction. We prove the analog of Katok’s theorem in the framework of Borel dynamics and show that, likewise, all free Borel $\mathbb {R}^{d}$Rd -flows emerge from $\mathbb {Z}^{d}$Zd -actions through the special flow construction using bi-Lipschitz cocycles.

This paper considers the problem of computing an optimal trajectory for an autonomous system that is subject to a set of potentially conflicting rules. First, we introduce the concept of prioritized safety specifications, where each rule is expressed as a temporal logic formula with its associated weight and priority. The optimality is defined based on the violation of such prioritized safety specifications. We then introduce a class of temporal logic formulas called si-FLTLGX and develop an efficient, incremental sampling-based approach to solve this minimum-violation planning problem with guarantees on asymptotic optimality. We illustrate the application of the proposed approach in autonomous vehicles, showing that si-FLTLGX formulas are sufficiently expressive to describe many traffic rules. Finally, we discuss practical considerations and present simulation results for a vehicle overtaking scenario.

Free Borel $\mathbb{R}^d$Rd-flows are smoothly equivalent if there is a Borel bijection between the phase spaces that maps orbits onto orbits and is a $C^\infty$C∞-smooth orientation preserving diffeomorphism between orbits. We show that all free non-tame Borel $\mathbb{R}^d$Rd-flows are smoothly equivalent in every dimension $d \ge 2$d≥2. This answers a question of B. Miller and C. Rosendal.

We consider the shortest path problem on graphs with weights taking values in Cartesian products of cost monoids. Such cost structures appear in multiobjective planning including, for instance, the minimum-violation planning framework. It is known that these products often do not satisfy the conditions of a cost monoid. Classical dynamic programming graph search algorithms may therefore fail to find an optimal solution. We isolate the concept of a regular cost monoid and propose an iterative search algorithm that finds an optimal path in graphs weighted by products of such costs. Our algorithm allows this class of multiobjective planning problems to be solved in polynomial time.

The behavior of self-driving cars must be compatible with an enormous set of conflicting and ambiguous objectives, from law, from ethics, from the local culture, and so on. This paper describes a new way to conveniently define the desired behavior for autonomous agents, which we use on the self-driving cars developed at nuTonomy. We define a "rulebook" as a pre-ordered set of "rules", each akin to a violation metric on the possible outcomes ("realizations"). The rules are partially ordered by priority. The semantics of a rulebook imposes a pre-order on the set of realizations. We study the compositional properties of the rulebooks, and we derive which operations we can allow on the rulebooks to preserve previously-introduced constraints. While we demonstrate the application of these techniques in the self-driving domain, the methods are domain-independent.

Any free Borel flow is shown to admit a cross section with only two possible distances between adjacent points. Non smooth flows are proved to be Lebesgue orbit equivalent if and only if they admit the same number of invariant ergodic probability measures.

This paper addresses the notion of time change equivalence for Borel $\mathbb{R}^d$Rd-flows. We show that all free $\mathbb{R}^d$Rd-flows are time change equivalent up to a compressible set. An appropriate version of this result for non-free flows is also given.

The main result of the paper is classification of free multidimensional Borel flows up to Lebesgue Orbit Equivalence, by which we understand an orbit equivalence that preserves the Lebesgue measure on each orbit. Two non smooth Euclidean flows are shown to be Lebesgue Orbit Equivalence if and only if they admit the same number of invariant ergodic probability measures.

We construct Graev ultrametrics on free products of groups with two-sided invariant ultrametrics and HNN extensions of such groups. We also introduce a notion of a free product of general Polish groups and prove, in particular, that two Polish groups $G$G and $H$H can be embedded into a Polish group $T$T in such a way that the subgroup of $T$T generated by $G$G and $H$H is isomorphic to the free product $G*H$G∗H.

We give a construction of two-sided invariant metrics on free products (possibly with amalgamation) of groups with two-sided invariant metrics and, under certain conditions, on HNN extensions of such groups. Our approach is similar to the Graev's construction of metrics on free groups over pointed metric spaces.

A homomorphism from a completely metrizable topological group into a free product of groups whose image is not contained in a factor of the free product is shown to be continuous with respect to the discrete topology on the range. In particular, any completely metrizable group topology on a free product is discrete.

We show that every two-dimensional class of topological similarity, and hence every diagonal conjugacy class of pairs, is meager in the group of order preserving bijections of the rationals and in the group of automorphisms of the randomly ordered rational Urysohn space.

We reexamine the Riemann Rearrangement Theorem for different types of convergence and classify possible sum ranges for statistically convergent series and for series that converge along the 2n-filter.