When an autonomous agent—whether a mobile robot, an aerial drone, or a high-precision laser scanner—needs to visit multiple locations in physical space, a simple greedy strategy ("go to the nearest unvisited point") inevitably fails. Greedy choices lead to severe backtracking, wasted energy, and mechanical latency. To achieve global efficiency, researchers across robotics, manufacturing, and experimental optimization reframe physical path planning as a combinatorial optimization problem: the Traveling Salesman Problem (TSP). By mapping spatial coordinates and physical constraints to nodes and edge weights, agents can compute globally optimized sequences that minimize total travel time, distance, or energy.
Why Global Sequencing Beats Greedy Decisions
Consider a robot tasked with inspecting ten points on a circuit board. A greedy algorithm simply looks at the robot's current position and moves to the closest unvisited point. While the first few moves are fast, the robot eventually traps itself into a corner, forcing a long, inefficient journey across the entire board to reach the final remaining points.
By framing the problem as a Traveling Salesman Problem, the system shifts from a local, reactive paradigm to a global, proactive one. The entire sequence is planned upfront by evaluating the complete cost matrix of transitions between all pairs of points. This global perspective allows the agent to accept a slightly longer immediate move if it prevents a massive backtracking penalty later.
Discretizing Physical Space into Graphs
To transform a continuous physical environment into a discrete graph suitable for combinatorial optimization, the target locations must first be defined as nodes. In robotic exploration and coverage tasks, this is often achieved by establishing a stable set of sensing points or grid cells across the workspace, as explored by Keisuke Ichikawa et al. in Region Exploration Planning for a Mobile Robot Using Reaction-Diffusion Equation on a Graph and by Yusuke Fukazawa et al. in Region exploration path planning for a mobile robot expressing working environment by grid points. Similarly, realistic robot exploration paths can be synthesized by sampling traversable points within a 3D occupancy grid and solving for the optimal visiting order, a technique utilized by Pavel Kirsanov et al. in DISCOMAN: Dataset of Indoor SCenes for Odometry, Mapping And Navigation.
However, physical tasks often involve more than just visiting isolated points; they may require traversing specific paths or handling continuous visibility regions. To accommodate these constraints, the graph representation must be adapted:
- Mandatory Segments: If an agent must traverse specific line segments (e.g., in inspection or routing), each segment can be mapped to a triplet of nodes. By assigning highly prohibitive weights to edges that break the segment sequence, any valid tour is mathematically forced to traverse the required paths completely, as shown by Masoud Safilian et al. in An Approximation Algorithm for the Subpath Planning Problem.
- Continuous Visibility Sets: When a surveillance drone only needs to get close enough to a target to see it, the problem transforms into a Generalized Traveling Salesperson Problem (GTSP). Here, the drone selects exactly one sampled configuration per target visibility set, discretizing a continuous routing problem into a solvable combinatorial framework, as demonstrated by Jeffrey R. Peters et al. in Unmanned Aerial Vehicle Surveillance Under Visibility and Dwell-Time Constraints.
Adapting to Domain Constraints via TSP Variants
Real-world operations rarely match the textbook TSP, where an agent visits every node exactly once and returns to the origin over a symmetric distance matrix. Researchers modify the underlying TSP formulation to match specific physical realities:
- Open-Loop and Asymmetric Routing: In e-commerce fulfillment centers, manual operators or robots perform multi-stop picking sequences where returning to the origin is unnecessary, as detailed by Azimbek Khudoyberdiev et al. in A Study of the Man and Unmanned Teaming System for Improving Efficiency in a Fulfillment Center. Similarly, in autonomous aerial reconstruction, the cost of moving between viewpoints depends heavily on the drone's orientation and camera rotation speed, making the underlying cost matrix directional. This is modeled as an asymmetric TSP to minimize total flight distance over predicted uncovered surfaces, as proposed by Chen Feng et al. in PredRecon: A Prediction-boosted Planning Framework for Fast and High-quality Autonomous Aerial Reconstruction.
- Clustered and Subset Selection: When an agent cannot visit every location due to energy or time constraints, formulations like the Traveling Salesman Subset-tour Problem (TSSP) allow data-collecting robots to optimize their routes over a subset of critical nodes, as shown by Ourania Tsilomitrou et al. in Mobile Data-Mule Optimal Path Planning for Wireless Sensor Networks. For cinematic drone videography, global trajectory planning can be framed as a Set TSP, where each landmark represents a cluster of potential camera moves, and the algorithm selects the optimal sequence and specific move to maximize smoothness, as developed by Bojian Wu et al. in Full 3D reconstruction of transparent objects. Automated surveillance for emergency response can also be modeled as a multi-dimensional routing problem across space and time using TSP variations to coordinate drone movements, as shown by Quan Li et al. in MaraVis: Representation and Coordinated Intervention of Medical Encounters in Urban Marathon.
- Ratio Optimization: Instead of minimizing distance alone, autonomous exploration can be modeled as a Minimum Ratio Traveling Salesman Problem (MRTSP). This formulation optimizes a sequence of targets by maximizing the ratio of newly explored area to distance traveled, preventing short-sighted local backtracking, as demonstrated by Chunyang Liu et al. in Enhancing autonomous exploration for robotics via real time map optimization and improved frontier costs. In underwater environments, sub-region trajectory optimization treats local coverage as a TSP to minimize redundant travel between non-equidistant sampling points, as shown by Xukai Mu in Coverage path planning for multi-AUV considering ocean currents and sonar performance.
Solving the Optimization and Reaping Physical Benefits
Because the TSP and its variants are NP-hard, finding exact solutions in real-time is computationally prohibitive. Instead, systems rely on metaheuristics and approximate solvers to find near-optimal paths rapidly.
Simulated annealing is widely used for real-time mobile hardware itinerary generation, as seen in the work of J. W. Li et al. in DESIGN AND IMPLEMENTATION OF SCENIC INTELLIGENT GUIDE SYSTEM BASED ON WECHAT APPLET, and in industrial manufacturing, such as optimizing PCB component dispensing paths to drastically reduce travel distance and time, as shown by Xiang Liu et al. in Fully Automated Dispensing System Based on Machine Vision.
Genetic algorithms are similarly leveraged to optimize multi-stage material handling logistics, as described by Cuiping Wen et al. in Research on Operation Optimization Problem of Material Handling System for Large Ship, and to design smart line-scanning trajectories for two-photon calcium imaging, prioritizing target dwell time over scanning empty space, as developed by Monica Moroni et al. in SmaRT2P: a software for generating and processing smart line recording trajectories for population two-photon calcium imaging. Early industrial automation architectures also relied on convex hull initializations and edge-exchange heuristics to minimize robotic end-effector travel during inspection routines, as shown by Jeffrey M. Becker et al. in An Architecture for Intelligent Task Automation.
The benefits of this combinatorial abstraction extend far beyond traditional robotics:
- Biological Screening: In high-throughput biological screening, solving an approximate TSP minimizes the mechanical latency of scanning hardware moving between discrete coordinates, as demonstrated by Rosana S. Molina et al. in High throughput instrument to screen fluorescent proteins under two-photon excitation.
- State Transitions: In multi-armed bandit problems with heterogeneous transition costs, solving for the shortest path that visits active states minimizes the total cost of state transitions, as shown by David Simchi-Levi et al. in Phase Transitions and Cyclic Phenomena in Bandits with Switching Constraints.
- Bayesian Optimization: In Bayesian Optimization (BO), treating a batch of promising experimental points as nodes in a TSP—as seen in the SnAKe framework—drastically reduces physical or temporal transition costs (such as equipment stabilization times), allowing physical search spaces to be optimized using half the resources of cost-agnostic methods, as established by Jose Pablo Folch et al. in SnAKe: Bayesian Optimization with Pathwise Exploration.
- Facility Deployment: For mobile facility routing over multi-step horizons, trajectories can be evaluated using set cover formulations to ensure equitable coverage, as shown by Da Qi Chen et al. in Efficient and Equitable Deployment of Mobile Vaccine Distribution Centers.
Key Foundational Work
Region Exploration Planning for a Mobile Robot Using Reaction-Diffusion Equation on a Graph (2002) — contributed 1 concept elements to this direction.
An Architecture for Intelligent Task Automation (1987) — contributed 1 concept elements to this direction.