Trajectory-Safe Orienteering for Human-Robot Shared Environments

Trajectory-Safe Orienteering for Human-Robot Shared Environments Songqun Gao1,3, Elena Basei2,3, Marco Roveri2,3, Luigi Palopoli2,3, Daniele Fontanelli1,3 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 highquality 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 collisionfree 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. I. INTRODUCTION The Orienteering Problem (OP) is a classic combinatorial optimization problem with broad impact in factory scheduling, logistics, and robot planning. Recent progress on OP and its variants has largely come from two directions: (i) metaheuristics [1] that orchestrate multi-stage search procedures tailored to specific COP variants, and (ii) neural combinatorial optimization (NCO) methods [2], [3] that leverage graph neural networks (GNN), Transformers, and other architectures to improve solution quality. However, these methods struggle to ensure that the solution remains feasible and collision-free when multiple agents share the same workspace in real applications. Task and motion planning (TAMP) [4] can simultaneously consider the motion feasibility of a robot during task execution; it can also dynamically adjust the task plan when a task fails. However, TAMP methods still struggle to guarantee efficient completion of assigned tasks. In our work, we consider scenarios where robots share workspaces with humans: assuming the human trajectory is globally known, the robot is required to avoid the human while adjusting its plan without compromising the orientation task score. The problem is formulated as OP with time windows and variable profits (OPTWVP), and a learning-based approach, namely, DEcoupled discreteContinuous Optimization with Service-time-guided Trajectory (DeCoST), is proposed to effectively solve OPTWVP in shared workspaces. Specifically, the contribution of this work is given by: This work is supported by the EU project Magician (Grant Agreement n. 101120731). 1Department of Industrial Engineering, Universit` a di Trento, Trento, Italy. [email protected]. 2Department of Information Engineering and Computer Science, Universit` a di Trento, Trento, Italy. 3Interdepartmental Robotics Labs (IDRA), University of Trento. •DeCoST is proposed to decouple the discrete and continuous decision (service times) variables, which improves the inference speed and quality of the OPTWVP solution. •The safety-aware time windows of nodes and the discretized workspace are introduced to ensure collisionfree trajectories between the end effector and the human. •DeCoST is validated through preliminary results, demonstrating its ability to generate collision-free trajectory plans while preserving the task quality. II. METHODOLOGY A. Reinforcement Learning-based Orienteering Solver In this work, DeCoST is proposed to effectively decouple the discrete and continuous decision variables in the OPTWVP problem, while enabling efficient and learnable coordination between them. In the first stage, a parallel decoding structure is employed to predict the path and the initial service time allocation. The second stage optimizes the service times through linear programming (LP) formulation and provides a long-horizon learning of service time estimation. We rigorously prove the global optimality of the second-stage solution. Experiments on OPTWVP instances demonstrate that DeCoST outperforms both state-of-the-art constructive solvers and the latest meta-heuristic algorithms in terms of solution quality and computational efficiency, achieving up to 6.6x inference speedup. Moreover, the proposed framework is compatible with various constructive solvers and consistently enhances the solution quality for OPTWVP. B. Collision Avoidance based on Time Windows The next step of this work is to integrate dynamic obstacle information into the graph representation. In this way, DeCoST is able to simultaneously search for an optimal orienteering plan and ensure that the resulting path is executable by the manipulator. Assume the human trajectory is globally known during the task execution period. We evaluate the potential collisions between the human trajectory and the nodes in the graph. For any time interval during which a collision with the human trajectory occurs, the corresponding time window of the affected node is considered closed. Through this method, the information of dynamic obstacles in the workspace can be mapped onto the time window constraints of the nodes, thereby ensuring collision avoidance during the solution of the orienteering problem. 2025 I-RIM Conference October 17-19, Rome, Italy ISBN: 9788894580570 10.5281/zenodo.17629746 119 C. Trajectory Generation In addition, to provide an executable solution for the manipulator, the two-dimensional workspace is discretized into M routing nodes, which are uniformly distributed over the workspace with a fixed resolution. These nodes are further embedded into the graph representation, and the graph nodes can be categorized into two types: routing nodes and profitable nodes. The routing node is an intermediate node and has no profit, p=0, while the profitable node is the place of interest relative to the task with p>0. During the solution phase, the agent reaches corresponding profitable nodes through routing nodes. Since the time windows of each node incorporate information about dynamic obstacles in the workspace, arriving at the target node during an open time window ensures the generated trajectory avoids collisions with moving objects. Based on the waypoints generated by DeCoST, we collect intermediate nodes between different profitable nodes for trajectory generation. Based on these nodes, a motion plan for the robot is then generated to execute. III. RESULTS AND DISCUSSION A. Performance Evaluation of DeCoST To comprehensively evaluate the performance of the DeCoST framework on the extended OPTWVP problem, we compare it against several representative baselines, with results summarized in Table I. The results show that DeCoST consistently achieves strong performance in all settings. It outperforms other heuristic and NCO methods in terms of solution quality (Score and Gap), while maintaining high computational efficiency. Although runtime rises, the substantial increase in solution quality demonstrates that precise optimization of service time is crucial for achieving a better solution. TABLE I PERFORMANCE ON OPTWVP WITH LARGE-SCALE CONFIGURATION (NUMBER OF NODES = 500). BOLD VALUES INDICATE THE BEST RESULT. Method Score ↑Gap ↓Runtime (ms) ↓ 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 B. Performance Evaluation on Trajectory Generation We conducted a comparative experiment between our DeCoST and Branch & Cut from a commercial solver, Gurobi. We used Gurobi to obtain the optimal score of the original OPTWVP (without workspace discretization, i.e., without routing nodes). As shown in Table II, the gap between the two solutions is only 3.72%, indicating that despite our approach considering workspace discretization to generate collision-free paths, it does not compromise the orienteering 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. problem’s score excessively. Additionally, our method is approximately 12 times faster than Gurobi, demonstrating its efficiency. Meanwhile, we conducted preliminary simulations of our proposed approach. In the setup, the moving obstacle is considered as an upper arm of a human, and humans and robots share the same workspace. The human is assumed to stand in front of the table and extend their upper arm into the workspace. Simulation setup is shown in Fig. 1. Simulations show that our method allows the end-effector to avoid human motion in the workspace while still achieving a high orienteering score. Simulation results show that our method enables the end effector to avoid human motion in the shared workspace while still maintaining high orienteering scores. This indicates its potential to efficiently route between different points of interest and to enhance the efficiency and adaptability of robot planning in human-robot shared workspaces. TABLE II PERFORMANCE EVALUATION AGAINST THE ORIGINAL OPTWVP. BOLD VALUES INDICATE THE BEST RESULT. Method Score ↑Gap ↓Runtime (ms) ↓ Branch & Cut 31.07 0.00% 1010 DeCoST 29.91 3.72% 79.46 REFERENCES [1] E. Marzal and L. Sebastia, ”Solving the tourist trip design problem with time windows and variable profit using incremental local search,” Appl. Soft Comput., vol. 155, p. 111399, 2024. [2] M. Kim, S. Choi, H. Kim, J. Son, J. Park, and Y. Bengio, ”Ant colony sampling with GFlowNets for combinatorial optimization,” Proc. 28th Int. Conf. Artif. Intell. Stat., 2025. [3] K. Y. D. Kwon, J. Choo, B. Kim, et al., ”Pomo: Policy optimization with multiple optima for reinforcement learning,” Advances in Neural Information Processing Systems, vol. 33, pp. 21188-21198, 2020. [4] T. Pan, R. Shome and L. E. Kavraki, ”Task and Motion Planning for Execution in the Real,” in IEEE Transactions on Robotics, vol. 40, pp. 3356-3371, 2024. 120