IRG TRO code

Note: this file is best viewed in a markdown viewer, e.g. https://github.com/joeyespo/grip.

Dependencies

This code was tested with Ubuntu 22.04. The following packages are used, with the shown version numbers, though other version numbers may work

julia 1.11.6. The precompilation statements provided in the julia repositories only seem to work for this julia version. If you want to use a different julia version, you can set use_sysimage = False in scripts/glns_juliacall.py and the code will probably work fine. Later in this readme, we explain how to precompile sysimages for GLNS and PGLNS to avoid just-in-time compilation occurring during an experiment and counting against the planning time budget. However, before running a planner on an instance, we solve a dummy GTSP which eliminates most of the just-in-time compilation time anyway, so we do not expect your results to be affected much by setting use_sysimage = False.

ROS2 Humble

Python 3.10.12

colcon (install via "sudo apt install python3-colcon-common-extensions")

pip (install via "sudo apt install python3-pip")

drake 1.26.0-1: https://drake.mit.edu/apt.html

Install via apt, and after installing, add the following to ~/.bashrc

export PATH="/opt/drake/bin${PATH:+:${PATH}}"
export LD_LIBRARY_PATH="/opt/drake/lib${LD_LIBRARY_PATH:+:${LD_LIBRARY_PATH}}"

pip install numba==0.61.0
pip install git+https://github.com/rdesc/pydubins.git
pip install gurobipy==11.0.3
pip install graphviz==0.20.3
pip install scipy==1.14.1
pip install opencv-python==4.10.0.84
pip install shapely==2.0.6
pip install pybind11==2.11.1
pip install juliacall==0.9.27
pip install drake==1.36.0

The irg_tro_code folder should be located in the src folder of a ROS2 workspace. Upon cloning this repo, go to the root directory of the repo and run

mkdir -p data/tmp

The repository https://bitbucket.org/dharabor/pathfinding/src/master/ needs to be cloned into a folder located at "~/polyanya", i.e. the "anyangle" folder in the linked repo must be contained at "~/polyanya/anyangle". Then you need to go into polyanya/anyangle/polyanya and run

make fast

Then go into polyanya/anyangle/polyanya/utils and run

make fast

The irg_tro_code also requires https://github.com/ryanhaining/cppitertools to be cloned into "~/".

Another dependency is Gurobi (we used 11.0.3). Follow the instructions here: https://support.gurobi.com/hc/en-us/articles/4534161999889-How-do-I-install-Gurobi-Optimizer. We require the full installation, not python only. Put the gurobi1103 folder in the "~" directory.

Now create the following symlinks

sudo ln -sf /usr/include/eigen3/Eigen /usr/local/include/Eigen
sudo ln -sf /usr/include/eigen3/unsupported /usr/local/include/unsupported

Then go to the ROS2 workspace folder and run

colcon build --cmake-args -DCMAKE_BUILD_TYPE=Release -Dpybind11_DIR=/opt/drake/lib/cmake/pybind11

Before running any of the below code, the ROS2 workspace containing irg_tro_code needs to be sourced, e.g.

source $HOME/ros2_ws/install/local_setup.bash

In our work, we have the above line in ~/.bashrc.

For the robot arm MT-TSP, the repository https://github.com/kuka-isir/iiwa_description must be cloned at "~/iiwa_description". Additionally, the files in iiwa_description_extra_files within the multimedia attachment must be placed into their corresponding folders in iiwa_description. For example, iiwa_description_extra_files/urdf/iiwa7.urdf must be placed in iiwa_description/urdf.

This code requires a folder ~/GLKH-1.1/GTSPLIB/ to exist. It also requires "~/GLNS_lazy_edge_eval.jl" to contain the contents of the GLNS_lazy_edge_eval.jl folder in the multimedia attachment, and it requires "~/PGLNS.jl" to contain the contents of the PGLNS.jl folder in the multimedia attachment. This code also requires the sysimages to be built for GLNS_lazy_edge_eval.jl and PGLNS.jl. See the README in each of the respective folders to build the sysimages.

Generating Instances and Running Experiments

Throughout this code, IRG-PGLNS is referred to as single_gtsp or sg, and IRG-GLNS is referred to as single_gtsp_glns or sgg. The following text describes how to generate instances. We also provide the instances we used in the paper at this link: https://drive.google.com/drive/folders/1k6PbyXHXS2y4TYCky_kMAmz4k3ERyfOe?usp=sharing. For each folder at the link, e.g. the 02_16_2025 folder, a folder with the same name must be created in the data folder, and each zip file in the 02_16_2025 folder in the link must be downloaded to the local 02_16_2025 folder and unzipped. So for example, there should be a local folder at the path data/02_16_2025/cemt_tsp_instances_actually_uniform_sample_depot_pos.

Close-Enough MT-TSP

To generate instances for the close-enough MT-TSP, in cemt_tsp.py, set gen_instances = True on line 22, set run_no_planners = True on line 47, change "for num_targets in [50, 100, 150, 200]" on line 118 to "for num_targets in [200]", and change "for target_radius in [0, 4, 8, 12]" on line 119 to "for target_radius in [12]". We change these lines because we generate instances for other numbers of targets and target radii using a different script, using the 200-target instances generated in this script. Additionally, to re-tune any planners, we need to generate tuning instances, so change "for random_seed in list(range(10, 20)) + list(range(40, 50))" on line 115 to "for random_seed in list(range(50))". Then run

python3 cemt_tsp.py

After generating these instances for 200 targets with radius 12, generate instances for 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, and 150 targets by running

python3 reduce_num_targets_in_Rn_instances.py

To generate instances with 200 targets and radius 0, 4, and 8, run

python3 change_target_radii_in_close_enough_instances.py

After this, run the experiments for Sections VII.C to VII.E using saved tuning parameters, by reverting the above changes to cemt_tsp.py, then running

python3 cemt_tsp.py

To tune n_{rand, init} as in Section VII.B, change "for random_seed in list(range(10, 20)) + list(range(40, 50))" on line 115 of cemt_tsp.py to "for random_seed in list(range(10)) + list(range(20, 40))", change "for num_targets in [50, 100, 150, 200]" to "for num_targets in [200]" on line 118, change "for target_radius in [0, 4, 8, 12]" to "for target_radius in [0]" on line 119, set "num_points_per_target_init = 2" on line 195, set all booleans to False on lines 27 to 37, and set time_limit = 3600 on line 57. Then run

python3 cemt_tsp.py

This will generate a folder in the "data" folder based on the date and time when the tuning was started, e.g. if we started tuning on February 16 2025 at 7:49am, 48s after the minute mark, we would see a folder "data/02_16_2025/init_trj_cemt_tsp_20250216-074948/". Then in check_max_points_used.py, replace 'data/02_16_2025/init_trj_cemt_tsp_20250216-074948/' on line 39 with whatever folder actually got generated. Then run

python3 check_max_points_used.py

to print out the tuned n_{rand, init} value. On line 195 of cemt_tsp.py, then set num_points_per_target_init equal to the tuned value.

To tune n_rand and alpha_term as in Section VII.B, need to first generate initial feasible tours for the tuning instances. To do so, change "for random_seed in list(range(10, 20)) + list(range(40, 50))" on line 115 of cemt_tsp.py to "for random_seed in list(range(10))", and set all booleans to False on lines 27 to 37. Then run

python3 cemt_tsp.py

This will generate a folder formatted similarly to the folder described above , e.g. "data/02_16_2025/init_trj_cemt_tsp_20250216-074948/". Then, in line 36 of tune_cemt_tsp.py, replace "data/06_04_2025/init_trj_cemt_tsp_20250604-145717/" with the folder that actually got generated. Then run

python3 tune_cemt_tsp.py

For each planner, this will generate files planner_name_best_point_num_cemt_tsp.npy and planner_name_best_num_iterations_cemt_tsp.npy, where planner_name will be the name of the planner in lowercase, i.e. pcg for PCG, single_gtsp for IRG-PGLNS, single_gtsp_glns for IRG-GLNS, and pdg for PDG. best_point_num is n_rand, and best_num_iterations is alpha_term.

To tune the memetic algorithm for the close-enough MT-TSP, as done in Section VII.B, run

python3 cemt_tsp_tune_memetic.py

This will save a file memetic_best_pop_size_multiplier_cemt_tsp.npy containing the best alpha_pop.

To run the experiments for the close-enough MT-TSP comparing initial tour generation methods from Section VII.I, run

python3 cemt_tsp_compare_init_trj_methods.py

To improve the tours generated by the initial tour generation methods in the script above, run the following command, where DAG-DFS should be replaced by PGLNS, GLNS, or IP to use initial tours from PGLNS, GLNS, or integer programming, respectively, and kept the same to use initial tours from DAG-DFS.

python3 cemt_tsp_improve_tours_from_initial_tour_experiment.py DAG-DFS

Before running the above script, lines 60 to 66 need to be populated with the saved initial tour data obtained by running cemt_tsp_compare_init_trj_methods.py.

Variable-Speed Dubins MT-TSP

To generate instances for the variable-speed Dubins MT-TSP, in vsdmt_tsp.py, set gen_instances = True on line 26, set run_no_planners = True on line 51, change "for num_targets in [50, 100, 150, 200]" on line 120 to "for num_targets in [200]", and change "for vmin_agent in [2., 3., 4., 5.]" on line 133 to "for vmin_agent in [2.]". We change these lines because we generate instances for other numbers of targets and minimum speeds using a different script, using the 200-target instances generated in this script. Additionally, to re-tune any planners, we need to generate the tuning instances, so change "for random_seed in list(range(10)) + list(range(40, 50))" on line 115 to "for random_seed in list(range(50))". Then run

python3 vsdmt_tsp.py

After generating these instances for 200 targets with min speed 2, generate instances for 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, and 150 targets by running

python3 reduce_num_targets_in_vsdmt_tsp_instances.py

To generate instances with 200 targets and vmin = 3, 4, and 5, run

python3 change_agent_vmin_in_vsdmt_tsp_instances.py

After this, run the experiments for sections VII.B to VII.D, and VII.F, using saved tuning parameters, by reverting the above changes to vsdmt_tsp.py, then running

python3 vsdmt_tsp.py

To tune n_{rand, init} as in Section VII.B, change "for random_seed in list(range(10)) + list(range(40, 50))" on line 118 of vsdmt_tsp.py to "for random_seed in list(range(10, 40))", change "for num_targets in [50, 100, 150, 200]" on line 120 to "for num_targets in [200]", change "for vmin_agent in [2., 3., 4., 5.]" on line 133 to "for vmin_agent in [5.]", set "num_points_per_target_init = 2" on line 215, set all booleans to False on lines 32 to 36, and set time_limit = 3600 on line 106. Then run

python3 vsdmt_tsp.py

This will generate a folder in the "data" folder based on the date and time when the tuning was started, e.g. "data/02_16_2025/init_trj_vsdmt_tsp_20250216-074948/". Then in check_max_points_used.py, replace 'data/02_16_2025/init_trj_cemt_tsp_20250216-074948/' on line 39 with whatever folder actually got generated. Then run

python3 check_max_points_used.py

to print out the tuned n_{rand, init} value. On line 215 of vsdmt_tsp.py, then set num_points_per_target_init equal to the tuned value.

To tune n_rand and alpha_term as in Section VII.B, need to first generate initial feasible tours for the tuning instances. To do so, change "for random_seed in list(range(10)) + list(range(40, 50))" on line 118 of vsdmt_tsp.py to "for random_seed in list(range(10, 20))", and set all booleans to False on lines 32 to 36. Then run

python3 vsdmt_tsp.py

This will generate a folder formatted similarly to the folder described above , e.g. "data/02_16_2025/init_trj_vsdmt_tsp_20250216-074948/". Then, in line 26 of tune_vsdmt_tsp.py, replace "data/02_16_2025/init_trj_cemt_tsp_20250216-074948/" with the folder that actually got generated. Then run

python3 tune_vsdmt_tsp.py

As in tune_cemt_tsp.py, for each planner, this will generate files planner_name_best_point_num_vsdmt_tsp_min_dist.npy and planner_name_best_num_iterations_vsdmt_tsp_min_dist.npy, where planner_name will be the name of the planner in lowercase.

To tune the memetic algorithm for the variable-speed Dubins MT-TSP, as done in Section VII.B, run

python3 vsdmt_tsp_tune_memetic.py

This will save a file memetic_best_pop_size_multiplier_vsdmt_tsp_min_dist.npy containing the best alpha_pop.

To run the experiments for the variable-speed Dubins MT-TSP comparing initial tour generation methods from Section VII.I, run

python3 vsdmt_tsp_compare_init_trj_methods.py

To improve the tours generated by the initial tour generation methods in the script above, run the following command, where DAG-DFS should be replaced by PGLNS, GLNS, or IP to use initial tours from PGLNS, GLNS, or integer programming, respectively, and kept the same to use initial tours from DAG-DFS.

python3 vsdmt_tsp_improve_tours_from_initial_tour_experiment.py

Before running the above script, lines 60 to 66 need to be populated with the saved initial tour data obtained by running vsdmt_tsp_compare_init_trj_methods.py.

Robot Arm MT-TSP

To generate instances for the robot arm MT-TSP, in mt_tsp_ra.py, set gen_instances = True on line 31, set run_no_planners = True on line 70, change "for num_targets in [50, 100, 150, 200]" on line 141 to "for num_targets in [200]", and change "for vmax_val in [4.1, 4.4, 4.7, 5.0]" on line 142 to "for vmax_val in [5.0]". We change these lines because we generate instances for other numbers of targets and max joint speeds using a different script, using the 200-target instances generated in this script. Additionally, to re-tune any planners, we need to generate the tuning instances, so change "for random_seed in list(range(10)) + list(range(40, 50))" on line 134 to "for random_seed in list(range(50))". Then run

python3 mt_tsp_ra.py

After generating these instances for 200 targets with max joint speed 5, generate instances for 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, and 150 targets by running

python3 reduce_num_targets_in_arm_instances.py

To generate instances with 200 targets and max joint speed = 4.1, 4.4, and 4.7, run

python3 change_vmax_in_arm_instances.py

After this, run the experiments for sections VII.B to VII.D, and VII.G, using saved tuning parameters, by reverting the above changes to mt_tsp_ra.py, then running

python3 mt_tsp_ra.py

To tune n_{rand, init} as in Section VII.B, change "for random_seed in list(range(10)) + list(range(40, 50))" on line 134 of mt_tsp_ra.py to "for random_seed in list(range(10, 40))", change "for num_targets in [50, 100, 150, 200]" on line 141 to "for num_targets in [200]", change "for vmax_val in [4.1, 4.4, 4.7, 5.0]" on line 142 to "for vmax_val in [4.1]", set "num_points_per_target_init = 2" on line 258, set all booleans to False on lines 37 to 44, and set time_limit = 3600 on line 61. Then run

python3 mt_tsp_ra.py

This will generate a folder in the "data" folder based on the date and time when the tuning was started, e.g. "data/02_16_2025/init_trj_mt_tsp_ra_20250216-074948/". Then in check_max_points_used.py, replace 'data/02_16_2025/init_trj_cemt_tsp_20250216-074948/' on line 39 with whatever folder actually got generated. Then run

python3 check_max_points_used.py

to print out the tuned n_{rand, init} value. On line 258 of mt_tsp_ra.py, then set num_points_per_target_init equal to the tuned value.

To tune n_rand and alpha_term as in Section VII.B, need to first generate initial feasible tours for the tuning instances. To do so, change "for random_seed in list(range(10)) + list(range(40, 50))" on line 134 of mt_tsp_ra.py to "for random_seed in list(range(10, 20))", and set all booleans to False on lines 37 to 44. Then run

python3 mt_tsp_ra.py

This will generate a folder formatted similarly to the folder described above , e.g. "data/02_16_2025/init_trj_mt_tsp_ra_20250216-074948/". Then, in line 28 of tune_mt_tsp_ra.py, replace "data/06_04_2025/init_trj_mt_tsp_ra_20250604-145819/" with the folder that actually got generated. Then run

python3 tune_mt_tsp_ra.py

As in tune_cemt_tsp.py, for each planner, this will generate files planner_name_best_point_num_mt_tsp_ra.npy and planner_name_best_num_iterations_mt_tsp_ra.npy, where planner_name will be the name of the planner in lowercase.

To run the experiments for the robot arm MT-TSP comparing initial tour generation methods from Section VII.I, run

python3 mt_tsp_ra_compare_init_trj_methods.py

To improve the tours generated by the initial tour generation methods in the script above, run the following command, where DAG-DFS should be replaced by PGLNS, GLNS, or IP to use initial tours from PGLNS, GLNS, or integer programming, respectively, and kept the same to use initial tours from DAG-DFS.

python3 mt_tsp_ra_improve_tours_from_initial_tour_experiment.py

Before running the above script, lines 66-68 and line 80 need to be populated with the saved initial tour data obtained by running mt_tsp_ra_compare_init_trj_methods.py.

Comparing to Optimal MICP

To run the experiments comparing IRG-PGLNS and PCG to the optimal MICP in Section VII.H, we need to first generate the corresponding instances. To do so, in test_sampling_against_micp_gcs.py, set gen_instances = True on line 19, set run_no_planners = True on line 37, and change "for num_targets in [10, 20, 30, 40]" on line 132 to "for num_targets in [40]". Then run

python3 test_sampling_against_micp_gcs.py

After this, in reduce_num_targets_in_Rn_instances.py, replace data/02_16_2025/cemt_tsp_instances_actually_uniform_sample_depot_pos/ on lines 75 and 76 with data/03_25_2025/mt_tsp_instances_test_against_micp_gcs/, set initial_num_targets = 40 on line 80, replace list(range(10, 20)) on line 84 with list(range(10)) + list(range(40, 50)), set target_rad_options = [0.] on line 90, and replace "for num_targets in [150, 120, 110, 100, 90, 80, 70, 60, 50, 40, 30, 20, 10]" on line 177 with "for num_targets in [30, 20, 10]". Then run

python3 reduce_num_targets_in_Rn_instances.py

After this, revert changes to test_sampling_against_micp_gcs.py and run

python3 test_sampling_against_micp_gcs.py

How data is saved

Whenever one of the experiment scripts above is run, we will get a folder looking like data/09_08_2025/pcg_cemt_tsp_20250908-224153/, where each subfolder in this folder is a particular instance with a particular set of planner parameters (e.g. number of processes).

Plotting

Plotting scripts are in the plotting_scripts directory.

The scripts ending in auc.py generate the plots and tables where we report AUC in the paper. The scripts ending in cost_vs_time.py generate the plots in the paper where we plot solution cost vs. planning time. The scripts ending in timing_breakdown.py generate the plots in the paper where we report different components of IRG-PGLNS's computation time. The scripts ending in init_trj.py generate the plots in the paper where we compare the runtime and cost for different methods of generating an initial feasible solution.

In the scripts ending in auc.py, set vary_num_targets = True to generate the latex code to make the tables like the ones in the paper reporting AUC for different numbers of targets. Set vary_num_proc = True to make plots of AUC vs. number of cores. In cemt_tsp_auc.py, set vary_target_radius = True to plot AUC vs. target radius for the close-enough MT-TSP. In vsdmt_tsp_auc.py, set vary_vmin = True to plot AUC vs. the agent's min speed in the Variable-Speed Dubins MT-TSP instances. In mt_tsp_ra_auc.py, set vary_vmax = True to plot AUC vs. the max joint speed for the robot arm MT-TSP. When one of these variables beginning with "vary" is set to True, the others should be set to False in the script. In the scripts ending in init_trj.py, set vval_option = 'comp_time' to plot computation time vs. number of targets, and set vval_option = 'cost' to plot cost vs. number of targets.

The data used for plotting is determined by variables ending in experiment_paths in each script. For example, if we want to use PCG data from data/09_08_2025/pcg_cemt_tsp_20250908-224153/ in cemt_tsp_auc.py, we would specify

pcg_experiment_paths = [repo_path + '/data/09_08_2025/pcg_cemt_tsp_20250908-224153/']

Sometimes we end up running an experiment in piecemeal, e.g. we run instances 0 to 9 one day, and instances 10 to 19 another day. This is why pcg_experiment_paths is a list. We specify each data folder comprising the overall data, i.e.

pcg_experiment_paths = [repo_path + '/data/09_08_2025/pcg_cemt_tsp_20250908-224153/', repo_path + '/data/09_09_2025/pcg_cemt_tsp_20250909-083535/']

Visualizing Instances and Solutions

To visualize a close-enough MT-TSP instance along with the known feasible trajectory generated alongside the instance, go into cemt_tsp.py, set just_visualize = True, set do_visualize = True, and modify the random seed, number of targets, and target radius at the top according to the instance you want. If you specify several random seeds, numbers of targets, or target radii to iterate through as you would during an experiment, the final instance will be visualized. Then run

python3 cemt_tsp.py

If you set just_visualize = False, then this will visualize the trajectory of the final planner run on the final instance specified above. The procedure for visualizing a variable-speed Dubins MT-TSP instance or planner solution is analagous, where the changes now need to be made to vsdmt_tsp.py.

Visualizing an instance or planner solution for the robot arm MT-TSP requires making the analagous changes to mt_tsp_ra.py, but before running mt_tsp_ra.py, you need additional steps. First, when performing visualization of the arm for the first time, in rviz/iiwa7_ros2_poly_targets.rviz, change /home/user/ros2_ws/src/irg_tro_code/urdf/iiwa7.urdf to point to urdf/iiwa7.urdf in this repo. Next, every time you want to visualize the arm (not just the first time), in another terminal, navigate to the launch folder in this repo and run the launch file there, i.e. if you are in the same folder of this readme,

cd launch
ros2 launch iiwa7_launch_poly_targets.py

Finally,

python3 mt_tsp_ra.py

will perform the visualization assuming you set do_visualize = True in mt_tsp_ra.py.

Generating instances and trajectories for physical robot experiments

For the physical robot experiments, instance generation and trajectory generation is similar to the procedures with cemt_tsp.py. In particular, running the following command will generate instances and trajectories for PCG, the ablations, and baseline presented in the paper:

python3 cemt_tsp_turtlebot.py

Note that in instance generation script invoked by cemt_tsp_turtlebot.py (generate_mt_tsp_mp_o_instance_turtlebot.py), we attempt to make the spline target trajectories stay inside the boundaries defined by map_lb and map_ub, where map_lb[0] indicates the smallest x-value we want a target's trajectory to undertake, map_ub[0] indicates the largest x-value, map_lb[1] is the smallest y-value, and map_ub[1] is the largest y-value. We do this because in the experimental setup, there are objects the robot may collide with outside these boundaries. This is a step that is specifically for the physical robot experiment instances, and the step is not present in the other instance generation scripts.