Diffusion models have shown great potential in generating trajectory plans for agents in environments with unknown dynamics. However, such models provide no safety guarantees. In this work, we focus on risk-aware planning with respect to safety constraints and introduce a probabilistically risk-aware variant of Diffuser (PRA-Diffuser). The diffusion model initially learns a distribution over trajectories that may or may not be unsafe. We then fine-tune this model to reduce the probability of sampling such unsafe trajectories. We analyze the proposed solution and introduce a provable lower bound on risk of safety violation leveraging concentration inequalities for conditional Value-at-Risk. Our approach can be applied to models that have been pre-trained, potentially from datasets containing unsafe trajectories. Our empirical results demonstrate that our approach significantly reduces unsafe trajectories generated by the diffusion model across multiple environments.

We study multi-agent reinforcement learning (MARL) under temporally extended Signal Temporal Logic(STL) objectives, which require reasoning over both long-horizon dynamics and inter-agent relations. Wepropose TD-MAT, a transformer-based architecture with multivariate positional encodings, causal temporalmasking, and a decomposed reward based on arithmetic–geometric mean robustness with variance regularization. Experiments on coordination tasks ranging from unstructured multi-objective problems to strict temporalsequencing show that TD-MAT learns effective long-term behaviors and generalizes to heterogeneous agentsettings. Ablation studies highlight the necessity of temporal masking, positional encodings, and reward decomposition, while comparisons to MAPPO, RMAPPO, and MAT reveal that transformers provide the greatestbenefit on unstructured, long-horizon tasks.

Contains fulltext : 331392.pdf (Publisher’s version ) (Open Access)

State-of-the-art radiotherapy machines with integrated magnetic resonance (MR) imaging, known as MR-Linacs, provide the capability to track tumors in real time. This capability aids delivery of precise irradiation in the presence of patient motion, such as breathing, by adjusting the radiation beam. However, current solutions rely solely on geometric tracking without closing the loop by considering the actual endpoint-the delivered radiation (here called dose). Real-time dose-based adaptation within a single session remains highly challenging due to the immense dimensionality of the problem. To overcome this, we have developed a radiotherapy simulator and propose a novel reinforcement learning (RL)-based approach for real-time adaptive radiotherapy using 2D fluence, as a surrogate to 3D dose. To our knowledge, this is the first application of RL in real-time adaptive radiotherapy. Our in-silico experiments showed the feasibility of using RL to close the feedback loop, dynamically adapting to patient motion and minimizing discrepancies between delivered and intended dose in clinical cases. Our approach introduces a new treatment delivery paradigm, enabling delivery based on a reference fluence and motion without predefined machine settings.

Real-world human-robot interactions often encompass uncertainty. This uncertainty can be handled in different ways, for example by designing robot planners to be more or less risk-tolerant. However, how users actually perceive different risk-taking behaviours in robots has yet to be described. Additionally, in the absence of guarantees on optimal robot performance, the interaction between risk and performance on user perceptions is also unclear. To address this gap, we conducted a user study with 84 participants investigating how robot performance and risk behaviour affects users' trust and risk-taking decisions. Participants collaborated with a Franka robot arm to perform a block-stacking task. We compared a robot which displays consistent but sub-optimal behaviours to a robot displaying risky but occasionally optimal behaviour. Risky robot behaviour led to higher trust than consistent behaviour when the robot was on average good at stacking blocks (high expectation), but lower trust when the robot was on average bad at stacking blocks (low expectation). Individual risk-willingness also predicted likelihood of selecting the risky robot over the consistent robot for future interactions, but only when the average expectation was low. These findings have implications for risk-aware planning and decision-making in mixed human-robot systems.

Informative path planning (IPP) applied to bathy-metric mapping allows AUVs to focus on feature-rich areas to quickly reduce uncertainty and increase mapping efficiency. Existing methods based on Bayesian optimization (BO) over Gaussian Process (GP) maps work well on small scenarios but they are short-sighted and computationally heavy when mapping larger areas, hindering deployment in real applications. To overcome this, we present a 2-layered BO IPP method that performs non-myopic, online planning in a tree search fashion over large Stochastic Variational GP maps, while respecting the AUV dynamical constraints and accounting for localization uncertainty. Our framework outperforms the standard industrial lawn-mowing pattern and a myopic baseline in a set of hardware in the loop (HIL) experiments in an embedded platform over real bathymetry areas.

Useful robot control algorithms should not only achieve performance objectives but also adhere to hard safety constraints. Control Barrier Functions (CBFs) have been developed to provably ensure system safety through forward invariance. However, they often unnecessarily sacrifice performance for safety since they are purely reactive. Receding horizon control (RHC), on the other hand, consider planned trajectories to account for the future evolution of a system. This work provides a new perspective on safety-critical control by introducing Forward Invariance in Trajectory Spaces (FITS). We lift the problem of safe RHC into the trajectory space and describe the evolution of planned trajectories as a controlled dynamical system. Safety constraints defined over states can be converted into sets in the trajectory space which we render forward invariant via a CBF framework. We derive an efficient quadratic program (QP) to synthesize trajectories that provably satisfy safety constraints. Our experiments support that FITS improves the adherence to safety specifications without sacrificing performance over alternative CBF and NMPC methods.

Uncertainties in contact dynamics and object geometry remain significant barriers to robust robotic manipulation. Caging helps mitigate these uncertainties by constraining an object’s mobility without requiring precise contact modeling. Existing caging research often treats morphology and policy optimization as separate problems, overlooking their synergy. In this paper, we introduce CageCoOpt, a hierarchical framework that jointly optimizes manipulator morphology and control policy for robust caging-based manipulation. The framework employs reinforcement learning for policy optimization at the lower level and multitask Bayesian optimization for morphology optimization at the upper level. We incorporate a caging metric into both optimization levels to encourage caging configurations and thereby improve manipulation robustness. The evaluation consists of four manipulation tasks and demonstrates that co-optimizing morphology and policy improves task performance under uncertainties, establishing caging-guided co-optimization as a viable approach for robust manipulation.

In this work we present RoDgeR, a system that leverages edge computing to offload computationally demanding tasks for real-time human-robot interaction (HRI). We identify dialogue management as an example of a computationally intensive task and demonstrate that an edge-based Large Language Model (LLM) results in faster response times than both cloud-based and embedded LLMs. We further implement an edge-based LLM in RoDgeR to evaluate user experience with 63 participants in a simulated restaurant scenario. Our results confirm that RoDgeR outperforms embedded and cloud-based solutions, leading to improved user experience. These findings highlight the potential of edge computing for improving the quality of human-robot interactions.

The paper considers the route planning problem for a vehicle with limited capacity operating in a road network. The vehicle is assigned a set of transportation requests that are more complex than traveling between two locations, may involve dependencies between their sub-tasks, and include deadlines and priorities. The requests arrive gradually over the deployment time-horizon, and thus replanning is needed for new requests. We address cases when not all requests can be serviced by their deadlines despite car sharing. We introduce multiple quality measures for plans that account for requests' delays with respect to deadlines and priorities. We formalize the problem as planning in a weighted transition system under syntactically co-safe LTL formulas. We develop an online planning and replanning algorithm based on the automata-based approach to least-violating plan synthesis and on translation to a Mixed Integer Linear Program (MILP). Furthermore, we show that the MILP reduces to graph search for a subclass of quality measures that satisfy a monotonicity property. We show the approach in simulations, including a case study on the mid-Manhattan road network over the span of 24 hours.

Partial observability and uncertainty are common problems in sequential decision-making that particularly impede the use of formal models such as Markov decision processes (MDPs). However, in practice, agents may be able to employ costly sensors to measure their environment and resolve partial observability by gathering information. Moreover, imprecise transition functions can capture model uncertainty. We combine these concepts and extend MDPs to robust active-measuring MDPs (RAM-MDPs). We present an active-measure heuristic to solve RAM-MDPs efficiently and show that model uncertainty can, counterintuitively, let agents take fewer measurements. We propose a method to counteract this behavior while only incurring a bounded additional cost. We empirically compare our methods to several baselines and show their superior scalability and performance.

We present the integration of a Non-Axiomatic Reasoning System (NARS) with mobile robots for planning and decision making. NARS enables robots to effectively handle uncertainty in real-time with complete sensor and actuator integration, thereby ensuring adaptability to evolving scenarios. We discuss essential parts of the logic, the architecture and working principles of NARS, and the integration of NARS as a ROS node. A case study is provided demonstrating the system’s proficiency to carry out a garbage collection task in an open-air environment by operating a mobile robot with manipulator arm, and we demonstrate its ability to learn about the place-dependent accumulation of garbage items. Case study also reveals that our approach performs more effectively on the overall task than the Belief-Desire-Intention model we compared with.

In environments like offices, the duration of a robot’s navigation between two locations may vary over time. For instance, reaching a kitchen may take more time during lunchtime since the corridors are crowded with people heading the same way. In this work, we address the problem of routing in such environments with tasks expressed in Metric Interval Temporal Logic (MITL) – a rich robot task specification language that allows us to capture explicit time requirements. Our objective is to find a strategy that maximizes the temporal robustness of the robot’s MITL task. As the first step towards a solution, we define a Mixed-integer linear programming approach to solving the task planning problem over a Varying Weighted Transition System, where navigation durations are deterministic but vary depending on the time of day. Then, we apply this planner to optimize for MITL temporal robustness in Markov Decision Processes, where the navigation durations between physical locations are uncertain, but the time-dependent distribution over possible delays is known. Finally, we develop a receding horizon planner for Markov Decision Processes that preserves guarantees over MITL temporal robustness. We show the scalability of our planning algorithms in simulations of robotic tasks.

Limited visibility and sensor occlusions pose pressing safety challenges for advanced driver-assistance systems (ADAS) and autonomous vehicles (AVs). In this work, our pursuit was to strike a balance: a method that ensures safety in occluded scenarios while preventing overly cautious behavior. We argue that such approaches are crucial for AVs’ future, particularly when navigating alongside human drivers on highways at high speeds. To this end, we used reachability analysis to find safe velocity bounds on occluded traffic participants. Compared to state-of-the-art methods, we achieved velocity increases in more than 60% of the 230 cut-in scenarios from the highD dataset, without sacrificing safety.

This paper addresses the problem of safety-critical control of autonomous robots, considering the ubiquitous uncertainties arising from un-modeled dynamics and noisy sensors. To take into account these uncertainties, probabilistic state estimators are often deployed to obtain a belief over possible states. Namely, Particle Filters (PFs) can handle arbitrary non-Gaussian distributions in the robot’s state. In this work, we define the belief state and belief dynamics for continuous-discrete PFs and construct safe sets in the underlying belief space. We design a controller that provably keeps the robot’s belief state within this safe set. As a result, we ensure that the risk of the unknown robot’s state violating a safety specification, such as avoiding a dangerous area, is bounded. We provide an open-source implementation as a ROS2 package and evaluate the solution in simulations and hardware experiments involving high-dimensional belief spaces.

Practical implementations of deep reinforcement learning (deep RL) have been challenging due to an amplitude of factors, such as designing reward functions that cover every possible interaction. To address the heavy burden of robot reward engineering, we aim to leverage subjective human preferences gathered in the context of human-robot interaction, while taking advantage of a baseline reward function when available. By considering baseline objectives to be designed beforehand, we are able to narrow down the policy space, solely requesting human attention when their input matters the most. To allow for control over the optimization of different objectives, our approach contemplates a multi-objective setting. We achieve human-compliant policies by sequentially training an optimal policy from a baseline specification and collecting queries on pairs of trajectories. These policies are obtained by training a reward estimator to generate Pareto optimal policies that include human preferred behaviours. Our approach ensures sample efficiency and we conducted a user study to collect real human preferences, which we utilized to obtain a policy on a social navigation environment.

In many real-world robotic scenarios, we cannot assume exact knowledge about a robot's state due to unmodeled dynamics or noisy sensors. Planning in belief space addresses this problem by tightly coupling perception and planning modules to obtain trajectories that take into account the environment's stochasticity. However, existing works are often limited to tasks such as the classic reach-avoid problem and do not provide risk awareness. We propose a risk-aware planning strategy in belief space that minimizes the risk of violating a given specification and enables a robot to actively gather information about its state. We use Risk Signal Temporal Logic (RiSTL) as a specification language in belief space to express complex spatio-temporal missions including predicates over Gaussian beliefs. We synthesize trajectories for challenging scenarios that cannot be expressed through classical reach-avoid properties and show that risk-aware objectives improve the uncertainty reduction in a robot's belief.

Signal Temporal Logic (STL) is a rigorous specification language that allows one to express various spatio-temporal requirements and preferences. Its semantics (called robustness) allows quantifying to what extent are the STL specifications met. In this work, we focus on enabling STL constraints and preferences in the Real-Time Rapidly Exploring Random Tree (RT-RRT*) motion planning algorithm in an environment with dynamic obstacles. We propose a cost function that guides the algorithm towards the asymptotically most robust solution, i.e. a plan that maximally adheres to the STL specification. In experiments, we applied our method to a social navigation case, where the STL specification captures spatio-temporal preferences on how a mobile robot should avoid an incoming human in a shared space. Our results show that our approach leads to plans adhering to the STL specification, while ensuring efficient cost computation.

Human-in-the-loop reinforcement learning (RL) methods actively integrate human knowledge to create reward functions for various robotic tasks. Learning from preferences shows promise as alleviates the requirement of demonstrations by querying humans on state-action sequences. However, the limited granularity of sequence-based approaches complicates temporal credit assignment. The amount of human querying is contingent on query quality, as redundant queries result in excessive human involvement. This paper addresses the often-overlooked aspect of query selection, which is closely related to active learning (AL). We propose a novel query selection approach that leverages variational autoencoder (VAE) representations of state sequences. In this manner, we formulate queries that are diverse in nature while simultaneously taking into account reward model estimations. We compare our approach to the current state-of-the-art query selection methods in preference-based RL, and find ours to be either on-par or more sample efficient through extensive benchmarking on simulated environments relevant to robotics. Lastly, we conduct an online study to verify the effectiveness of our query selection approach with real human feedback and examine several metrics related to human effort.

Rearranging objects is an essential skill for robots. To quickly teach robots new rearrangements tasks, we would like to generate training scenarios from high-level specifications that define the relative placement of objects for the task at hand. Ideally, to guide the robot's learning we also want to be able to rank these scenarios according to their difficulty. Prior work has shown how generating diverse scenario from specifications and providing the robot with easy-to-difficult samples can improve the learning. Yet, existing scenario generation methods typically cannot generate diverse scenarios while controlling their difficulty. We address this challenge by conditioning generative models on spatial logic specifications to generate spatially-structured scenarios that meet the specification and desired difficulty level. Our experiments showed that generative models are more effective and data-efficient than rejection sam-pling and that the spatially-structured scenarios can drastically improve training of downstream tasks by orders of magnitude.

In this article, we address the task and safety performance of data-driven model predictive controllers (DD-MPC) for systems with complex dynamics, i.e., temporally or spatially varying dynamics that may also be discontinuous. The three challenges we focus on are the accuracy of learned models, the receding horizon-induced myopic predictions of DD-MPC, and the active encouragement of safety. To learn accurate models for DD-MPC, we cautiously, yet effectively, explore the dynamical system with rapidly exploring random trees (RRT) to collect a uniform distribution of samples in the state-input space and overcome the common distribution shift in model learning. The learned model is further used to construct an RRT tree that estimates how close the model's predictions are to the desired target. This information is used in the cost function of the DD-MPC to minimize the short-sighted effect of its receding horizon nature. To promote safety, we approximate sets of safe states using demonstrations of exclusively safe trajectories, i.e., without unsafe examples, and encourage the controller to generate trajectories close to the sets. As a running example, we use abrokenversion of an inverted pendulum where the friction abruptly changes in certain regions. Furthermore, we showcase the adaptation of our method to a real-world robotic application with complex dynamics: robotic food-cutting. Our results show that our proposed control framework effectively avoids unsafe states with higher success rates than baseline controllers that employ models from controlled demonstrations and even random actions.

Reinforcement learning has shown great potential for learning sequential decision-making tasks. Yet, it is difficult to anticipate all possible real-world scenarios during training, causing robots to inevitably fail in the long run. Many of these failures are due to variations in the robot's environment. Usually experts are called to correct the robot's behavior; however, some of these failures do not necessarily require an expert to solve them. In this work, we query non-experts online for help and explore 1) if/how non-experts can provide feedback to the robot after a failure and 2) how the robot can use this feedback to avoid such failures in the future by generating shields that restrict or correct its high-level actions. We demonstrate our approach on common daily scenarios of a simulated kitchen robot. The results indicate that non-experts can indeed understand and repair robot failures. Our generated shields accelerate learning and improve data-efficiency during retraining.

This paper is interested in formalizing human trajectories in human-robot encounters. Inspired by robot navigation tasks in human-crowded environments, we consider the case where a human and a robot walk towards each other, and where humans have to avoid colliding with the incoming robot. Further, humans may describe different be-haviors, ranging from being in a hurry/minimizing completion time to maximizing safety. We propose a decision tree-based algorithm to extract STL formulae from multi-label data. Our inference algorithm learns STL specifications from data containing multiple classes, where instances can be labelled by one or many classes. We base our evaluation on a dataset of trajectories collected through an online study reproducing human-robot encounters.

Safe driving requires autonomous vehicles to anticipate potential hidden traffic participants and other unseen objects, such as a cyclist hidden behind a large vehicle, or an object on the road hidden behind a building. Existing methods are usually unable to consider all possible shapes and orientations of such obstacles. They also typically do not reason about observations of hidden obstacles over time, leading to conservative anticipations. We overcome these limitations by (1) modeling possible hidden obstacles as a set of states of a point mass model and (2) sequential reasoning based on reachability analysis and previous observations. Based on (1), our method is safer, since we anticipate obstacles of arbitrary unknown shapes and orientations. In addition, (2) increases the available drivable space when planning trajectories for autonomous vehicles. In our experiments, we demonstrate that our method, at no expense of safety, gives rise to significant reductions in time to traverse various intersection scenarios from the CommonRoad Benchmark Suite.

Two people walking towards each other in a colliding course is an everyday problem of human-human interaction. In spite of the different environmental and individual factors that might jeopardise successful human trajectories, people are generally skilled at avoiding crashing into each other. However, it is not clear if the same strategies will apply when a human is in a colliding course with a robot, nor which (if any) robot-related factors will influence the human's decision to swerve or not. In this work, we present the results of an online study where participants walked towards a virtual robot that differed in terms of anthropomorphism and perceived autonomy, and had to decide whether to swerve, or continue straight. The experiment was inspired by the game-theoretic game of chicken. We found that people performed more swerving actions when they believed the robot to be teleoperated by another participant. When they swerved, they also swerved closer to the robot with high levels of human-likeness, and farther away from the robot with low anthropomorphism score, suggesting a higher uncertainty about the mechanical-looking robot's intentions. These results are discussed in the context of socially-aware robot navigation, and will be used to design novel algorithms for robot trajectories that take robot-related differences into account.

Driving styles play a major role in the acceptance and use of autonomous vehicles. Yet, existing motion planning techniques can often only incorporate simple driving styles that are modeled by the developers of the planner and not tailored to the passenger. We present a new approach to encode human driving styles through the use of signal temporal logic and its robustness metrics. Specifically, we use a penalty structure that can be used in many motion planning frameworks, and calibrate its parameters to model different automated driving styles. We combine this penalty structure with a set of signal temporal logic formula, based on the Responsibility-Sensitive Safety model, to generate trajectories that we expected to correlate with three different driving styles: aggressive, neutral, and defensive. An online study showed that people perceived different parameterizations of the motion planner as unique driving styles, and that most people tend to prefer a more defensive automated driving style, which correlated to their self-reported driving style.

Unknown properties of a robot’s environment are one of the sources of uncertainty in autonomous navigation. This uncertainty has to be accounted for when modelling robot dynamics. For ground vehicles in particular, terrain structure is one of the main environmental factors that can strongly influence the dynamics. Therefore, to ensure the ability of a robot to safely and efficiently navigate new environments, robust motion planning and control systems are needed. This paper investigates a data-driven approach to planning and control based on construction of robust motion primitives (MPs) and corresponding feedback rules that ensure a bounded error along the planned trajectory. The approach is tested in an exploration scenario in which a robot systematically inspects an area consisting of several terrain types with the aim of recognizing changes in dynamical properties, learning new dynamics models when such changes are detected and recording that information for future use. The advantage of incorporating the collected data into motion planning in multi-terrain environments is illustrated via simulation.

In this paper, we are interested in formalizing human trajectories in human-robot encounters. We consider a particular case where a human and a robot walk towards each other. A question that arises is whether, when, and how humans will deviate from their trajectory to avoid a collision. These human trajectories can then be used to generate socially acceptable robot trajectories. To model these trajectories, we propose a data-driven algorithm to extract a formal specification expressed in Signal Temporal Logic with probabilistic predicates. We evaluated our method on trajectories collected through an online study where participants had to avoid colliding with a robot in a shared environment. Further, we demonstrate that probabilistic STL is a suitable formalism to depict human behavior, choices and preferences in specific scenarios of social navigation.

Ensuring the safety of autonomous vehicles (AV s) in uncertain traffic scenarios is a major challenge. In this paper, we address the problem of computing the risk that AV s violate a given safety specification in uncertain traffic scenarios, where state estimates are not perfect. We propose a risk measure that captures the probability of violating the specification and determines the average expected severity of violation. Using highway scenarios of the US101 dataset and Responsible Sensitive Safety (RSS) as an example specification, we demonstrate the effectiveness and benefits of our proposed risk measure. By incorporating the risk measure into a trajectory planner, we enable AVs to plan minimal-risk trajectories and to quantify trade-offs between risk and progress in traffic scenarios.

Autonomous systems are often required to operate in partially observable environments. They must reliably execute a specified objective even with incomplete information about the state of the environment. We propose a methodology to synthesize policies that satisfy a linear temporal logic formula in a partially observable Markov decision process (POMDP). By formulating a planning problem, we show how to use point-based value iteration methods to efficiently approximate the maximum probability of satisfying a desired logical formula and compute the associated belief state policy. We demonstrate that our method scales to large POMDP domains and provides strong bounds on the performance of the resulting policy.

In this paper we consider a fleet of self-driving cars operating in a road network governed by rules of the road, such as the Vienna Convention on Road Traffic, providing rides to customers to serve their demands with desired deadlines. We focus on the associated motion planning problem that trades-off the demands' delays and level of violation of the rules of the road to achieve social optimum among the vehicles. Due to operating in the same environment, the interaction between the cars must be taken into account, and can induce further delays. We propose an integrated route and motion planning approach that achieves scalability with respect to the number of cars by resolving potential collision situations locally within so-called bubble spaces enclosing the conflict. The algorithms leverage the road geometries, and perform joint planning only for lead vehicles in the conflict and use queue scheduling for the remaining cars. Furthermore, a framework for storing previously resolved conflict situations is proposed, which can be use for quick querying of joint motion plans. We show the mobility-on-demand setup and effectiveness of the proposed approach in simulated case studies involving up to 10 self-driving vehicles.

This work focuses on integrated routing and motion planning for an autonomous vehicle in a road network. We consider a problem in which customer demands need to be met within desired deadlines, and the rules of the road need to be satisfied. The vehicle might not, however, be able to satisfy these two goals at the same time. We propose a systematic way to compromise between delaying the satisfaction of the given demand and violating the road rules. We utilize scLTL formulas to specify desired behavior and develop a receding horizon approach including a periodically interacting routing algorithm and a RRT*-based motion planner. The proposed solution yields a provably minimum-violation trajectory. An illustrative case study is included.

In this paper, we study the decentralized control problem of a two-agent system under local goal specifications given as temporal logic formulas. The agents collaboratively carry an object in a leader-follower scheme and lack means to exchange messages on-line, i.e., to communicate explicitly. Specifically, we propose a decentralized control protocol and a leader re-election strategy that secure the accomplishment of both agents' local goal specifications. The challenge herein lies in exploiting exclusively implicit inter-robot communication that is a natural outcome of the physical interaction of the robots with the object. An illustrative experiment is included clarifying and verifying the approach.

We focus on autonomous robot action planning problem from Linear Temporal Logic (LTL) specifications, where the action refers to a “simple” motion or manipulation task, such as “go from A to B” or “grasp a ball”. At the high-level planning layer, we propose an algorithm to synthesize a maximally satisfying discrete control strategy while taking into account that the robot's action executions may fail. Furthermore, we interface the high-level plan with the robot's low-level controller through a reactive middle-layer formalism called Behavior Trees (BTs). We demonstrate the proposed framework using a NAO robot capable of walking, ball grasping and ball dropping actions.

We consider the problem of automatic control strategy synthesis, for discrete models of robotic systems, to fulfill a task that requires reaching a goal state while obeying a given set of safety rules. In this paper, we focus on the case when the said task is not feasible without temporarily violating some of the rules. We propose an algorithm that {synthesizes} a motion which violates only lowest priority rules for the shortest amount of time. Although the proposed algorithm can be applied in a variety of control problems, throughout the paper, we motivate this problem with an autonomous car navigating in an urban environment while abiding by the rules of the road, such as "always stay in the right lane" and "do not enter the sidewalk." We evaluate the algorithm on a case study with several illustrative scenarios.

We develop a technique to automatically generate a control policy for a robot moving in an environment that includes elements with partially unknown, changing behavior. The robot is required to achieve an optimal surveillance mission, in which a certain request needs to be serviced repeatedly, while the expected time in between consecutive services is minimized. We define a fragment of Linear Temporal Logic (LTL) to describe such a mission and formulate the problem as a temporal logic game. Our approach is based on two main ideas. First, we extend results in automata learning to detect patterns of the partially unknown behavior of the elements in the environment. Second, we employ an automata-theoretic method to generate the control policy.We show that the obtained control policy converges to an optimal one when the unknown behavior patterns are fully learned. We implemented the proposed computational framework in MATLAB. Illustrative case studies are included.

In this paper we present a method for automatically generating optimal robot trajectories satisfying high level mission specifications. The motion of the robot in the environment is modeled as a weighted transition system. The mission is specified by a general linear temporal logic formula. In addition, we require that an optimizing proposition must be repeatedly satisfied. The cost function that we seek to minimize is the maximum time between satisfying instances of the optimizing proposition. For every environment model, and for every formula, our method computes a robot trajectory which minimizes the cost function. The problem is motivated by robotic monitoring and data gathering. In this setting, the optimizing proposition is satisfied at locations where data can be uploaded, and the formula specifies a an infinite horizon data collection mission. Our method utilizes Büchi automata to produce an automaton (which can be thought of as a graph) whose runs satisfy the temporal logic formula. We then present a graph algorithm which computes a path corresponding to the optimal robot trajectory. We also present an implementation for a robot performing a data gathering mission.