Papers for

autonomous systems engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Symbolic method speeds probabilistic timing models verification hundredfold

Symbolic Abstraction Refinement

Abstract: Autonomous systems choose actions whose outcomes are uncertain and are subject to time constraints. Probabilistic timed automata (PTAs) model exactly this, and verifying one answers a question about the system's decision-making: the maximum probability of reaching a goal, or the minimum probability of reaching a hazard, that a controller can guarantee. Verification normally works over symbolic states, each pairing a discrete location with a region of clock values, and its difficulty is that the best behavior generally varies within such a region. The PRISM verifier's most capable PTA method responds by splitting regions until each is uniform, rebuilding the transitions that reach them and propagating the split backward through the state graph of a stochastic game, a cascade of graph reconstruction that partitions regions the property never depends on. We present SYMAR, which instead makes the value function symbolic: each symbolic state carries a function from sub-regions of its clock region to probability bounds, so refinement is the appearance of new sub-regions in that function, and previously generated states are never split nor their incoming transitions reconstructed. Both sources of PTA nondeterminism, the timing and the choice of actions, are captured implicitly by the preimage computation that produces those sub-regions. Heuristic forward search then bounds how much refinement is done at all, expanding an And-Or graph from the initial state along the most promising behaviors so that effort is confined to the property-relevant fragment, guided by bounds and preferred actions from a single unrefined run of the existing method; a partial-refinement backup keeps the otherwise combinatorial sub-region count lean, and every stored interval provably contains the true probability. On the PRISM PTA benchmarks, whose subproblems recur in autonomous systems (distributed agreement under contention, leader election, and self-configuration without central coordination), SYMAR is up to 108x faster, solves an instance on which the existing method exhausts the time limit, and is markedly less sensitive to the deadline constant, resolving one instance in a 37-node search graph, unchanged as the deadline triples, where the existing method needs 86,380 abstract states and 73 refinement rounds.

Tue 17 NovArtificial Intelligence
The gist
Verifying autonomous systems that make timed decisions with uncertain outcomes is complicated because their behavior can vary continuously over time. The authors introduce SYMAR, a new technique that represents time more flexibly and avoids repeatedly rebuilding complex parts of the system model. This approach narrows verification effort to the most relevant time ranges and outcomes, making it much faster and more scalable than previous methods. The authors show SYMAR works well on common benchmark problems involving decision-making without central control.
Open → 2611.22404v1

Petri nets reveal how binary neural networks make decisions

From Constraints to Causality: Petri net Encodings for Explaining Binary Neural Network Inference

Abstract: Binary Neural Networks (BNNs) are attractive for resource-constrained hardware and on-device components in autonomous systems. However, their discrete, non-linear behaviour makes them difficult to analyse and trust in safety-relevant settings. Existing approaches based on SAT and Satisfiability Modulo Theories can verify a BNN's input-output properties, but treat it as a monolithic constraint system, which reveal only whether a property holds and not how the computation reaches its result. In this paper, we present an early work that provides a complementary, discrete-event view. We give a compositional translation from the inference semantics of a fixed, trained BNN to a 1-safe Petri net (PN), where each computation step is an explicit transition, so that a firing sequence is a causal trace of the BNN's decision. On a worked example, we establish faithfulness via exhaustive input-output equivalence against a reference implementation, and show how contrasting firing sequences localises where a single-feature change alters the prediction. Finally, we outline two directions this opens: a correctness-of-translation theorem, and a causal-trace analysis of where two trained BNNs diverge in their decisions, a structural question that constraint-based verifiers cannot express.

Tue 17 NovLogic in Computer ScienceMachine Learning
The gist
Binary neural networks are simple AI models that work well on small devices, but they are tricky to understand because their decisions are based on complex, step-by-step calculations. The authors turn these calculations into a form called Petri nets, which show every step in the decision process clearly and in order. This helps explain exactly how changing one input feature can change the decision. Their method can also compare two different neural networks to see where their decisions differ.
Open → 2611.22396v1

Fast convergence of policies in zero sum markov games with limited feedback

Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback

Abstract: We study last-iterate convergence in unknown two-player zero-sum discounted Markov games with bandit feedback. The players learn independently along a single trajectory without observing each other's actions. We develop Adaptive Regularized TD Learning (ARTD), which achieves a $\widetilde{\mathcal{O}}(t^{-1/4})$ duality gap bound for the current policies under a uniform hitting time assumption, with high probability simultaneously over all rounds and starting states. This improves the $\widetilde{\mathcal{O}}(t^{-1/(9+ν)})$ rate of Cai et al. (2023), for any fixed $ν>0$, under the same feedback model and hitting time assumption. Our algorithm requires no knowledge of the hitting time bound, the time horizon, or the confidence level. To stabilize policy learning as value estimates change, we separate fast temporal difference averaging from bounded value updates. We adapt log-barrier regularization to the progress of value estimation, controlling both policy and value errors throughout learning. Together, these mechanisms enable fast convergence of the policies actually played, even when the players learn independently from bandit feedback.

Mon 5 OctMachine LearningComputer Science and Game Theory
The gist
This paper looks at how two players learn strategies over time when they compete in a zero-sum game, but can only see limited information from the game. The authors develop a new learning algorithm called Adaptive Regularized TD Learning (ARTD) that improves how quickly the players’ strategies converge to an equilibrium. Unlike previous methods, ARTD works without knowing some key parameters ahead of time, and it ensures stable learning even when the players update independently. This means the strategies played get better faster, even when players do not observe each other's moves directly.
Open → 2610.05968v1