Trajectory-Safe Orienteering for Human-Robot Shared Environments

Songqun Gao; Elena Basei; Marco Roveri; Luigi Palopoli; Daniele Fontanelli

cs.ROSep 28, 2026

Trajectory-Safe Orienteering for Human-Robot Shared Environments

Authors: Songqun Gao, Elena Basei, Marco Roveri, Luigi Palopoli, Daniele Fontanelli

Organizations: Department of Industrial Engineering, Universit`a di Trento, Trento, Italy. · Interdepartmental Robotics Labs (IDRA), University of Trento, Trento, Italy · Department of Information Engineering and Computer Science, Universit`a di Trento, Trento, Italy.

Abstract

Orienteering problem (OP) has wide real-world applications and also great potential in human-robot collaboration. However, existing approaches struggle to simultaneously ensure safe and feasible trajectories while achieving high-quality task execution in shared workspaces. To this end, this work studies the OP with time windows and variable profits (OPTWVP). A two-stage DEcoupled discrete-Continuous Optimization with Service-time-guided Trajectory (DeCoST) approach is proposed to effectively solve OPTWVP in shared spaces. Meanwhile, the safety-aware time windows of nodes and the discretized workspace are introduced to ensure collision-free trajectories between the end effector and the human. Preliminary results validate the effectiveness of DeCoST in generating collision-free trajectory plans while preserving the quality of orienteering tasks.

Figures & tables

Method	Score $\uparrow$	Gap $\downarrow$	Runtime (ms) $\downarrow$
Branch & Cut	82.3	0.00%	68400
ILS [ 1 ]	78.2	4.98%	8803
GFACS (Greedy) [ 2 ]	67.4	18.1%	112
GFACS	73.1	11.3%	9420
POMO [ 3 ]	58.6	28.8%	747
DeCoST (Ours)	79.6	3.31%	1329

TABLE I: Performance on OPTWVP with large-scale configuration (number of nodes = 500). Bold values indicate the best result.

Method	Score $\uparrow$	Gap $\downarrow$	Runtime (ms) $\downarrow$
Branch & Cut	31.07	0.00%	1010
DeCoST	29.91	3.72%	79.46

TABLE II: Performance evaluation against the original OPTWVP. Bold values indicate the best result.

Fig. 1: Simulation setup. We consider human and robot sharing the same workspace, and our proposed approach aims to find both an orienteering solution and a trajectory that is collision-free between the end effector and the human.

Explore similar work

Denoising Multi-Robot Trajectories
Sep 28, 2026Yuhao Zhang, Keisuke Okumura, Ajay Shankar +1Multi-Robot Motion Planning Multi-Robot Systems
Department of Computer Science and Technology, University of Cambridge, U.K. · National Institute of Advanced Industrial Science and Technology (AIST), Japan
Vision-Based Safe Human-Robot Collaboration with Uncertainty Guarantees
Apr 16, 2026Jakob Thumm, Marian Frei, Tianle Ni +2Human-Robot Collaboration Human Motion Prediction
Department of Aeronautics and Astronautics, Stanford University · Chair of Imaging and Computer Vision, RWTH Aachen University · School of Artificial Intelligence, Shanghai Jiao Tong University +1
Beyond Fixed Goal Delivery: Online POMDP Planning for Target Interception in Crowds
Jul 20, 2026Himanshu Gupta, Kelvin Aladum, Nisar Ahmed +2Planning Markov Decision Processes
Dept. of Aerospace Engineering Sciences, University of Colorado Boulder, USA · Dept. of Computer Science, University of Colorado Boulder, USA

Sep 28, 2026, cs.ROJ/K move · Enter open · S save

Denoising Multi-Robot Trajectories

Yuhao Zhang, Keisuke Okumura, Ajay Shankar, Amanda Prorok

Department of Computer Science and Technology, University of Cambridge, U.K. · National Institute of Advanced Industrial Science and Technology (AIST), Japan

Multi-Robot Motion Planning Multi-Robot Systems Denoising Diffusion Probabilistic Model

Open paper AskPDF arXiv

Multi-robot trajectory planning is a fundamental problem in multi-robot coordination but remains computationally challenging due to its nonconvex, multimodal, and high-dimensional nature. This work builds upon D4orm, a dynamics-aware diffusion-denoising framework, and develops a family of planning architectures for diverse operational requirements. Unlike conventional numerical optimization methods, D4orm employs sampling-based optimization to generate solution trajectories through massively parallel sampling, leveraging modern computing architectures such as GPUs. Its diffusion-denoising structure iteratively optimizes \textit{deformations} to candidate control trajectories, providing an efficient and versatile paradigm for generating kinodynamically feasible and conflict-free trajectories. Using D4orm as the building block for advanced planners, we present a decoupled planner for improved scalability, an online receding-horizon planner with feedback control, and a distributed planner for resource-constrained settings. Evaluations with differential-drive and holonomic robots in 2D and 3D environments demonstrate that D4orm-based approaches find high-quality solutions faster and more reliably than other sampling-based optimization methods, such as MPPI, as well as a learned diffusion-model-based method. We further demonstrate zero-shot deployment on ten real quadrotors with obstacles, large-scale deconfliction with 100 simulated robots, and fully onboard distributed `lifelong' operation with six ground robots. Overall, these results establish diffusion denoising as a scalable and reliable framework for multi-robot coordination. Code and video: https://github.com/proroklab/d4orm

Abstract

Explore similar work

Denoising Multi-Robot Trajectories

Vision-Based Safe Human-Robot Collaboration with Uncertainty Guarantees

Beyond Fixed Goal Delivery: Online POMDP Planning for Target Interception in Crowds