Risk-bounded motion planning in dynamic environments for autonomous driving presents complex challenges, particularly in solving the nonconvex problem of ensuring continuous, safe, and real-time navigation towards a destination. This paper introduces an online graph-based local planning approach constrained by a user-defined driving style in terms of a risk budget$\Delta$for the entire mission. Our online approach assigns a risk bound to each motion planning decision, ensuring that the total risk consumed remains within$\Delta$. First, we construct a spatial lattice graph that adheres to the vehicle's curvature constraints. Then, the trajectory planning problem is reformulated as an online optimization problem, where decisions must be made sequentially without prior knowledge of future events. Therefore, we propose a reduction to the problem to be online multiple-choice knapsack problem (ON-MCKP), where the knapsack items are candidate paths generated by solving constrained shortest-path problems. To solve the ON-MCKP, we deploy online algorithms that offer theoretical guarantees on the risk allocation throughout the entire mission. The effectiveness of our method is demonstrated empirically, showing significant improvements in the objective without violating safety constraints.

This paper addresses key limitations in recent 3D tracking-by-detection methods, focusing on the challenges of identifying legitimate trajectories and mitigating state estimation drift in the Kalman filter. Current methods rely heavily on threshold-based detection score filtering approaches to reduce false positives and prevent ghost trajectories. However, these approaches fail for distant and partially occluded objects, where detection scores drop, and false positives surpass that threshold. Additionally, many existing methods assume that detections provide precise localization, overlooking the inherent noise that affects localization accuracy and causes state drift for occluded objects, as demonstrated in this work. To this end, a novel track validity mechanism, combined with a multi-stage observational gating process, is proposed that significantly reduces ghost tracks and improves tracking performance. Our method achieves 29.47% enhancement in Multi-Object tracking accuracy (MOTA) on the KITTI validation dataset with the Second detector. Furthermore, a refined Kalman filter term mitigates localization noise, ensuring robust state estimation for objects that are occluded and superior recovery during prolonged occlusions. This results in higher-order tracking accuracy (HOTA) improving by 4.8% on the KITTI validation dataset with the PV-RCNN detector. The proposed online framework, RobMOT, outperforms state-of-the-art methods, including deep learning approaches, across multiple detectors, with HOTA improvements of up to 3.92% on the KITTI testing dataset and 8.7% on the KITTI validation dataset while achieving the lowest identity switch (IDSW) scores of 7 and 0, respectively. RobMOT excels under challenging scenarios, such as tracking distant objects and handling prolonged occlusions, surpassing state-of-the-art methods on the Waymo Open testing dataset with a 1.77% improvement in MOTA for objects at distances exceeding 50 meters. RobMOT achieves a groundbreaking runtime of 3221 FPS using a single CPU, establishing itself as a highly efficient and scalable solution for real-time multi-object tracking.

Risk-bounded motion planning for autonomous driving in dynamic environments presents significant research challenges. Ensuring continuous navigation towards a destination while making real-time decisions is a nonconvex problem. This paper presents a graph-based local planning method constrained by user-specific driving preference, represented as a risk-bound criterion for motion planning. First, we propose a lattice graph construction method that adheres to the vehicle's curvature constraints. Then, we formulate the trajectory planning problem as an integer-linear programming task, addressed by our novel risk-bounded and prediction-aware constrained shortest path. Our solution accounts for both static and dynamic obstacles in urban settings, adhering to traffic regulations. At the core of our approach is a conservative spatiotemporal risk assessment mechanism, which evaluates collisions considering the uncertain delay from speed control of the ego vehicle and predicted trajectories of dynamic obstacles. We implemented our solution using the CARLA simulator and the ROS2 platform, within a comprehensive framework encompassing global planning, local planning, and vehicle control. The effectiveness of our approach is demonstrated through notable collision avoidance, improved path-tracking, and enhanced risk-bounded planning capabilities.

Navigating autonomous vehicles efficiently across unstructured and off-road terrains remains a formidable challenge, often requiring intricate mapping or multi-step pipelines. However, these conventional approaches struggle to adapt to dynamic environments. This paper presents TerrainSense, an end-to-end framework that overcomes these limitations. By utilizing a transformers, TerrainSense detects lane semantics and topology from camera images, enabling mapless path planning without the reliance on highly detailed maps. The efficacy of TerrainSense was rigorously assessed on six diverse datasets, evaluating its efficacy in detection, segmentation, and path prediction using various metrics. Notably, it outperforms the other state-of-the-art methods by 9.32% in precisely predicting the path with 18.28% faster inference time.

The efficient navigation of autonomous vehicles across rugged and unstructured terrains remains a significant challenge. Most existing research in this area emphasizes the need for complex mappings or intricate multi-step methodologies. However, these traditional approaches often struggle to adapt to dynamic changes in environmental conditions. In this paper, we introduce PathFormer, an end-to-end framework designed specifically to address these challenges. PathFormer utilizes transformers to decode free-space semantics and configurations directly from camera images, enabling efficient path planning without the reliance on detailed, pre-existing maps. The performance of PathFormer was rigorously evaluated across diverse datasets, where it demonstrated superior capabilities, outperforming other state-of-the-art methods by 3.68% in precisely segmenting free-space regions and showing a 13.65% improvement in correctly predicting traversable paths.

Before the world-wide deployment of autonomous vehicles, it is essential to implement intermediate solutions with partial autonomy. One such solution is the use of vehicle teleoperation, the act of controlling a vehicle from a distance. In real time applications of teleoperation, it is often pertinent to use augmented reality components within the teleoperator view, which are referred to as a predictive display. In this work, we evaluate our predictive display method, which is a guiding path based on the free space in the environment. The path is generated based on our Dual Transformer Network (DTNet), which uses both object detection and lane semantic segmentation to define the free space in the environment. While the model has previously performed well on image data, it is necessary to observe its accuracy in the presence of time delay and packet loss, to assess its performance in a real-time setting. Thus, in this work, we use CARLA simulator to compare the detected free space on the teleoperator side to the true free space on the vehicle side across different values of time delay and packet loss. Under optimal network conditions, our model yielded a remarkable 87.9% DSC score and 81.3% IoU score. Defining our minimum performance threshold as 80% DSC and 70% IoU, we conclude that our model can effectively mitigate the challenges of time delay below 100ms and packet loss below 1%, both of which represent substantial tolerances.

The Partially Observable Markov Decision Process (POMDP) is widely used in probabilistic planning for stochastic domains. However, current extensions, such as constrained and chance-constrained POMDPs, have limitations in modeling real-world planning problems because they assume that all actions have a fixed duration. To address this issue, we propose a unified model that encompasses durative POMDP and its constrained extensions. To solve the durative POMDP and its constrained extensions, we first convert them into an Integer Linear Programming (ILP) formulation. This approach leverages existing solvers in the ILP literature and provides a foundation for solving these problems. We then introduce a heuristic search approach that prunes the search space, which is guided by solving successive partial ILP programs. Our empirical evaluation results show that our approach outperforms the current state-of-the-art fixed-horizon chance-constrained POMDP solver.

Decentralizing crowdsourcing using blockchain removes the trusted mediator who may cause social biases in data aggregation and uncertainties in ensuring proper rewards to workers. Permissionless blockchain discloses all data on public ledgers, which compromises the privacy and anonymity of workers and induces free-riders. State-of-the-art anonymous crowdsourcing systems enable anonymity through identity registration of workers and a trusted setup for key generation. However, these systems fail to support anonymous payments to workers, which may compromise the identities of workers. In this paper, we incorporate anonymous payments in crowdsourcing and dispense with identity registration and trusted setup to support open anonymous participation from any worker. Our solution is based on the decentralized anonymous payment systems (e.g., Zerocoin), commitment schemes, and efficient non-interactive zero-knowledge proofs.

Persistent multi-object tracking (MOT) allows autonomous vehicles to navigate safely in highly dynamic environments. One of the well-known challenges in MOT is object occlusion when an object becomes unobservant for subsequent frames. The current MOT methods store objects information, such as trajectories, in internal memory to recover the objects after occlusions. However, they retain short-term memory to save computational time and avoid slowing down the MOT method. As a result, they lose track of objects in some occlusion scenarios, particularly long ones. In this paper, we propose DFR-FastMOT, a light MOT method that uses data from a camera and LiDAR sensors and relies on an algebraic formulation for object association and fusion. The formulation boosts the computational time and permits long-term memory that tackles more occlusion scenarios. Our method shows outstanding tracking performance over recent learning and non-learning benchmarks with about 3% and 4% margin in MOTA, respectively. Also, we conduct extensive experiments that simulate occlusion phenomena by employing detectors with various distortion levels. The proposed solution enables superior performance under various distortion levels in detection over current state-of-art methods. Our framework processes about 7,763 frames in 1.48 seconds, which is seven times faster than recent benchmarks. The framework will be available at https://github.com/MohamedNagyMostafa/DFR-FastMOT.

Unmanned aerial vehicles (UAVs), commonly known as drones, are being increasingly deployed throughout the globe as a means to streamline monitoring, inspection, mapping, and logistic routines. When dispatched on autonomous missions, drones require an intelligent decision-making system for trajectory planning and tour optimization. Given the limited capacity of their onboard batteries, a key design challenge is to ensure the underlying algorithms can efficiently optimize the mission objectives along with recharging operations during long-haul flights. With this in view, the present work undertakes a comprehensive study on automated tour management systems for an energy-constrained drone: (1) We construct a machine learning model that estimates the energy expenditure of typical multi-rotor drones while accounting for real-world aspects and extrinsic meteorological factors. (2) Leveraging this model, the joint program of flight mission planning and recharging optimization is formulated as a multi-criteria Asymmetric Traveling Salesman Problem (ATSP), wherein a drone seeks for the time-optimal energy-feasible tour that visits all the target sites and refuels whenever necessary. (3) We devise an efficient approximation algorithm with provable worst-case performance guarantees and implement it in a drone management system, which supports real-time flight path tracking and re- computation in dynamic environments. (4) The effectiveness and practicality of the proposed approach are validated through extensive numerical simulations as well as real-world experiments. Note to Practitioners—This study is stimulated by the need for developing pragmatic and provably efficient automated tour management systems for UAVs deployed on energy-constrained, long-distance flight missions. As such, UAVs provide a nifty platform for facilitating environmental monitoring, disaster management, transport of medical supplies, as well as expediting last-mile deliveries. However, existing path planners generally fall short of capturing several crucial aspects, such as detailed power consumption model (e.g., factoring in payload, wind speed and direction) or performance guarantees, potentially leading to underutilized or infeasible routing decisions. To address these issues, the present work proposes a theoretically-backed routing approach with a certifiable degree of optimality and develops an effective, practical power consumption evaluation model for multi-rotor UAVs, verified on multiple drone models.

Aircraft routing problem is a crucial component for flight automation. Despite recent successes, challenges still remain when the environment is dynamic and uncertain. In this paper, we tackle the following two challenges. First, when the environment is uncertain, it is much safer if the route planner can guarantee a specified level of safety. Second, when the environment is dynamic, the planner needs to adapt to the changes in the environment quickly. To address these challenges, we present three contributions. First, we propose formulating the aircraft routing problem under a dynamic and uncertain environment as a chance constrained stochastic shortest path (CC-SSP) problem. Second, we introduce an anytime algorithm for the CC-SSP problem, which is effective in a dynamic environment with limited planning time. To be more specific, we present two versions of the algorithm and compare their performances. Third, we show that the algorithm can be generalized to solve a larger class of problems called chance constrained partially observable Markov decision process (CC-POMDP).

The Internet-of-Things (IoT) has engendered a new paradigm of integrated sensing and actuation systems for intelligent monitoring and control of smart homes and buildings. One viable manifestation is that of IoT-empowered smart lighting systems, which rely on the interplay between smart light bulbs (equipped with controllable LED devices and wireless connectivity) and mobile sensors (possibly embedded in users’ wearable devices such as smart watches, spectacles, and gadgets) to provide automated illuminance control functions tailored to users’ preferences (e.g., of brightness, color intensity, or color temperature). Typically, practical deployment of these systems precludes the adoption of sophisticated but costly location-aware sensors capable of accurately mapping out the details of a dynamic operational environment. Instead, cheap oblivious mobile sensors are often utilized, which are plagued with uncertainty in their relative locations to sensors and light bulbs. The imposed volatility, in turn, impedes the design of effective smart lighting systems for uncertain indoor environments with multiple sensors and light bulbs. With this in view, the present article sheds light on the adaptive control algorithms and modeling of such systems. First, a general model formulation of an oblivious multisensor illuminance control problem is proposed, yielding a robust framework agnostic to a dynamic surrounding environment and time-varying background light sources. Under this model, we devise efficient algorithms inducing continuous adaptive lighting control that minimizes energy consumption of light bulbs while meeting users’ preferences. The algorithms are then studied under extensive empirical evaluations in a proof-of-concept smart lighting testbed featuring LIFX programmable bulbs and smartphones (deployed as light sensing units). Lastly, we conclude by discussing the potential improvements in hardware development and highlighting promising directions for future work.

Partially Observable Markov Decision Process (POMDP) is a fundamental framework for planning and decision making under uncertainty. POMDP is known to be intractable to solve or even approximate when the planning horizon is long (i.e., within a polynomial number of time steps). Constrained POMDP (C-POMDP) allows constraints to be specified on some aspects of the policy in addition to the objective function. When the constraints involve bounding the probability of failure, the problem is called Chance-Constrained POMDP (CC-POMDP). Our first contribution is a reduction from CC-POMDP to C-POMDP and a novel Integer Linear Programming (ILP) formulation. Thus, any algorithm for the later problem can be utilized to solve any instance of the former. Second, we show that unlike POMDP, when the length of the planning horizon is constant, (C)C-POMDP is NP-Hard. Third, we present the first Fully Polynomial Time Approximation Scheme (FPTAS) that computes (near) optimal deterministic policies for constant-horizon (C)C-POMDP in polynomial time.

There is a fundamental tradeoff between the communication cost and the latency in information aggregation. Aggregating multiple communication messages over time can alleviate overhead and improve energy efficiency on one hand, but inevitably incurs information delay on the other hand. In the presence of uncertain future inputs, this tradeoff should be balanced in an online manner, which is studied by the classical dynamic TCP ACK problem for a single information source. In this paper, we extend dynamic TCP ACK problem to a general setting of collecting aggregate information from distributed and correlated information sources. In this model, distributed sources observe correlated events, whereas only a small number of reports are required from the sources. The sources make online decisions about their reporting operations in a distributed manner without prior knowledge of the local observations at others. Our problem captures a wide range of applications, such asin-situsensing, anycast acknowledgement, and distributed caching. We present simple threshold-based competitive distributed online algorithms under different settings of intercommunication. Our algorithms match the theoretical lower bounds in order of magnitude. We observe that our algorithms can produce satisfactory performance in simulations and practical test bed.

A challenge in future smart grid is how to efficiently allocate power among customers considering inelastic demands, when the power supply is constrained by the network or generation capacities. This problem is an extension to the classical knapsack problem in a way that the item values are expressed as non-positive real or complex numbers representing power demands, rather than positive real numbers. The objective is to maximize the total utility of the customers. Recently in Chau-Elbassioni-Khonji [AAMAS 14], a PTAS was presented for the case where the maximum phase angle between any pair of power demands is φ ≤ π/2; and a bi-criteria FPTAS when π/2 <; φ ≤ π - ε, for any polynomially small ε. For 0 ≤ φ ≤ π/2, Yu and Chau [AAMAS 13] showed that unless P=NP, there is no FPTAS. In this paper, we present important hardness results that close the approximation gap. We show that unless P=NP, there is no α-approximation for π/2 <; π ≤ π - ε, where a is any number with polynomial length. Moreover, for the case when φ is arbitrarily close to π, neither a PTAS nor any bi-criteria approximation algorithm with polynomial guarantees can exist. In this paper, we also present a natural generalization to a networked setting such that each edge in the transmission network can have a capacity constraint. We show that there is no bi-criteria approximation algorithm with polynomial guarantees for this networked setting, even all power demands are real (non-complex) numbers.

We study algorithm based fault tolerance techniques for supporting malicious errors in distributed computations based on Chinese remainder theorem. The description holds for both computations with integers or with polynomials over a field. It unifies the approaches of redundant residue number systems and redundant polynomial systems through the Reed Solomon decoding algorithm proposed by Gao. We propose several variations on the application of the extended Euclid algorithm, where the error correction rate is adaptive. Several improvements are studied, including the use of various criterions for the termination of the Euclidean Algorithm, and an acceleration using the Half-GCD techniques. When there is some redundancy in the input, a gap in the quotient sequence is stated at the step matching the error correction, which enables early termination parallel computations. Experiments are shown to compare these approaches.