PSPatrick Scheffe

Patrick Scheffe

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Patrick Scheffe has a total of 36 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Simultaneous Computation with Multiple Prioritizations in Multi-Agent Motion Planning

    by Patrick Scheffe, Julius Kahle, Bassam Alrifaee

    Multi-agent path finding (MAPF) in large networks is computationally challenging. An approach for MAPF is prioritized planning (PP), in which agents plan sequentially according to their priority. Albeit a computationally efficient approach for MAPF, the solution quality strongly depends on the prioritization. Most prioritizations rely either on heuristics, which do not generalize well, or iterate to find adequate priorities, which costs computational effort. In this work, we show how agents can compute with multiple prioritizations simultaneously. Our approach is general as it does not rely on domain-specific knowledge. The context of this work is multi-agent motion planning (MAMP) with a receding horizon subject to computation time constraints. MAMP considers the system dynamics in more detail compared to MAPF. In numerical experiments on MAMP, we demonstrate that our approach achieves near-optimal prioritization and outperforms state-of-the-art methods with only a minor increase in computation time. We show real-time capability in an experiment on a road network with ten vehicles in our Cyber-Physical Mobility Lab.


  • Small-Scale Testbeds for Connected and Automated Vehicles and Robot Swarms: Challenges and a Roadmap

    by Jianye Xu, Johannes Betz, Armin Mokhtarian, Archak Mittal, Mengchi Cai, Rahul Mangharam, Omar M. Shehata, Catherine M. Elias, Jan-Nico Zaech, Patrick Scheffe, et al.

    This article proposes a roadmap to address the current challenges in small-scale testbeds for connected and automated vehicles (CAVs) and robot swarms. The roadmap is a joint effort of participants in the workshop “First Workshop on Small-Scale Testbeds for Connected and Automated Vehicles and Robot Swarms,” held on 2 June at the IEEE Intelligent Vehicles Symposium (IV) 2024 in Jeju, South Korea. The roadmap contains three parts: 1) enhancing accessibility and diversity, especially for underrepresented communities, 2) sharing best practices for the development and maintenance of testbeds, and 3) global testbed connectivity, e.g., through an abstraction layer, to support collaboration. The workshop features invited speakers, contributed papers, and a presentation of a survey paper on testbeds. The survey paper provides an online comparative table of more than 25 testbeds, available at https://bassamlab.github.io/testbeds-survey. The workshop’s own website is available at https://cpm.lrt.unibw.de/workshop.


  • A Survey on Small-Scale Testbeds for Connected and Automated Vehicles and Robot Swarms: A Guide for Creating a New Testbed [Survey]

    by Armin Mokhtarian, Jianye Xu, Patrick Scheffe, Maximilian Kloock, Simon Schäfer, Heeseung Bang, Viet-Anh Le, Sangeet Ulhas, Johannes Betz, Sean Wilson, et al.

    Connected and automated vehicles (CAVs) and robot swarms (RSs) hold transformative potential for enhancing safety, efficiency, and sustainability in the transportation and manufacturing sectors. Extensive testing and validation of these technologies are crucial for their deployment in the real world. While simulations are essential for initial testing, they often have limitations in capturing the complex dynamics of real-world interactions. This limitation underscores the importance of small-scale testbeds. These testbeds provide a realistic, cost-effective, and controlled environment for testing and validating algorithms, acting as an essential intermediary between simulation and full-scale experiments. This work serves to facilitate researchers’ efforts in identifying existing small-scale testbeds suitable for their experiments and provide insights for those who want to build their own. In addition, it delivers a comprehensive survey of the current landscape of these testbeds. We derive 62 characteristics of testbeds based on the well-known sense–plan–act paradigm and offer an online table comparing 23 small-scale testbeds based on these characteristics. The online table is hosted on our designated public webpage, https://bassamlab.github.io/testbeds-survey, and we invite testbed creators and developers to contribute to it. We closely examine nine testbeds in this article, demonstrating how the derived characteristics can be used to present testbeds. Furthermore, we discuss three ongoing challenges concerning small-scale testbeds that we identified, i.e., small-scale to full-scale transition, sustainability, and power and resource management.


  • Open Access

    Limiting Computation Levels in Prioritized Trajectory Planning with Safety Guarantees

    by Jianye Xu, Patrick Scheffe, Bassam Alrifaee

    In prioritized planning for vehicles, vehicles plan trajectories in parallel or in sequence. Parallel prioritized planning offers approximately consistent computation time regardless of the number of vehicles but struggles to guarantee collision-free trajectories. Conversely, sequential prioritized planning can guarantee collision-freeness but results in increased computation time as the number of sequentially computing vehicles, which we term computation levels, grows. This number is determined by the directed coupling graph resulted from the coupling and prioritization of vehicles. In this work, we guarantee safe trajectories in parallel planning through reachability analysis. Although these trajectories are collision-free, they tend to be conservative. We address this by planning with a subset of vehicles in sequence. We formulate the problem of selecting this subset as a graph partitioning problem that allows us to independently set computation levels. Our simulations demonstrate a reduction in computation levels by approximately 64% compared to sequential prioritized planning while maintaining the solution quality.

  • Open Access

    Prioritized Trajectory Planning for Networked Vehicles Using Motion Primitives

    by Patrick Scheffe, Matheus V. A. Pedrosa, Kathrin Flaßkamp, Bassam Alrifaee

    The computation time required to solve nonconvex, nonlinear optimization problems increases rapidly with their size. This poses a challenge in trajectory planning for multiple networked vehicles with collision avoidance. In the centralized formulation, the optimization problem size increases with the number of vehicles in the networked control system (NCS), rendering the formulation unusable for experiments. We investigate two methods to decrease the complexity of networked trajectory planning. First, we approximate the optimization problem by discretizing the vehicle dynamics with an automaton, which turns it into a graph-search problem. Our search-based trajectory planning algorithm has a limited horizon to further decrease computation complexity. We achieve recursive feasibility by design of the automaton which models the vehicle dynamics. Second, we distribute the optimization problem to the vehicles with prioritized distributed model predictive control (P-DMPC), which reduces the problem size. To counter the incompleteness of P-DMPC, we propose a framework for time-variant priority assignment. The framework expands recursive feasibility to every vehicle in the NCS. We present two time-variant priority assignment algorithms for road vehicles, one to improve vehicle progress and one to improve computation time of the NCS. We evaluate our approach for online trajectory planning of multiple networked vehicles in simulations and experiments.

  • Open Access

    Designing Maneuver Automata of Motion Primitives for Optimal Cooperative Trajectory Planning

    by Matheus V. A. Pedrosa, Patrick Scheffe, Bassam Alrifaee, Kathrin Flaßkamp

    Trajectory planning techniques form a central step to enable autonomous driving. The motion primitives method generates an automaton of precomputed maneuvers with structure-exploiting properties. Thereby, the trajectory planning problem can be reduced to finding an admissible/optimal sequence of motion primitives. In this chapter, we present ways to designing maneuver automata based on different system models and on either analytical or data-based approaches for automaton generation. Moreover, numerical methods for computing optimal maneuvers are listed and we discuss graph-based planning techniques. A subsequent chapter shows the evaluation of motion primitives automata in the Cyber-Physical Mobility Lab.

  • Optimization-based motion primitive automata for autonomous driving

    by Matheus V. A. Pedrosa, Patrick Scheffe, Bassam Alrifaee, Kathrin Flaßkamp

    Trajectory planning for autonomous cars can be addressed by primitive-based methods, which encode nonlinear dynamical system behavior into automata. In this paper, we focus on optimal trajectory planning. Since, typically, multiple criteria have to be taken into account, multiobjective optimization problems have to be solved. For the resulting Pareto-optimal motion primitives, we introduce a universal automaton, which can be reduced or reconfigured according to prioritized criteria during planning. We evaluate a corresponding multi-vehicle planning scenario with both simulations and laboratory experiments.


  • Open Access

    Testing distributed trajectory planning in the cyber-physical mobility lab

    by Maximilian Kloock, Patrick Scheffe, Bassam Alrifaee

    This article presents the testing of distributed trajectory planning algorithms using our rapid prototyping platform, the Cyber-Physical Mobility Lab (CPM Lab). We propose two algorithms for distributed trajectory planning which plan trajectories at intersections, highway on- and off-ramps, and lane changes for networked and autonomous vehicles. The algorithms avoid collisions between vehicles using a synchronization-based and a prioritized Distributed Model Predictive Control (DMPC) strategy. We test two algorithms in the CPM Lab which is able to handle parallel, sequential, and hybrid computations. The CPM Lab achieves reproducible experiments under non-deterministic computation times and stochastic communication times. Our evaluation shows that different algorithms for distributed trajectory planning can be efficiently tested in different in-the-loop tests.


  • Open Access

    An Architecture for Experiments in Connected and Automated Vehicles

    by Maximilian Kloock, Patrick Scheffe, Ole Gress, Bassam Alrifaee

    Rapid prototyping of Connected and Automated Vehicles (CAV) is challenging because of the physical distribution of vehicles. Furthermore, experiments with CAV may be subject to external influences which prevent reproducibility. This article presents an architecture for the experimental testing of CAVs, focusing on decision-making. Our architecture for experiments of CAV is strictly modular and hierarchical, and therefore it supports an easy and rapid exchange of every single controller as well as of optimization libraries. Additionally, the architecture synchronizes the whole network of sensors, computation devices, and actuators. Thus, it achieves deterministic and reproducible results, even for time-variant network topologies. Using this architecture, we can include active and passive vehicles and vehicles with heterogeneous dynamics in the experiments. The architecture also allows for handling communication uncertainties, e.g., data packet drop and time delay. The resulting architecture supports performing different in-the-loop tests and experiments. We demonstrate the architecture in the Cyber-Physical Mobility Lab (CPM Lab) using 20 vehicles on a 1:18 scale. The architecture can be applied to other domains.


  • Open Access

    Reducing Computation Time with Priority Assignment in Distributed MPC

    by Patrick Scheffe, Julius Kahle, Bassam Alrifaee

    Distributing computations among agents in a networked control system (NCS) reduces computational effort. One distribution strategy is prioritized distributed model predictive control (P-DMPC). In P-DMPC, we couple and prioritize interacting agents to achieve a desired behavior of the NCS. We characterize the interaction with a directed acyclic graph (DAG). The computation time of the NCS is mainly determined through the longest path in the DAG. The longest path depends on the undirected coupling graph, which is fixed, and the prioritization, which is variable. The approaches to prioritize agents are numerous and pursue various goals. This article presents an approach to assign priorities in P-DMPC to reduce the longest path length in the coupling DAG and thus the computation time for the NCS. We prove that this problem can be mapped to a graph-coloring problem, in which the number of colors required corresponds to the longest path length in the coupling DAG. We further propose to reorder the colors, which decreases the number of constraints for agents along the longest path in the coupling DAG. We propose a decentralized graph-coloring algorithm to determine priorities for the agents. We evaluate the approach by applying it to trajectory planning for networked and autonomous vehicles on roads.