Improved ant colony optimization combined with MAKLINK-Dijkstra for safe UAV trajectory planning in dense urban building environments

Raising the collision-avoidance safety margin for low-altitude missions over dense building clusters inevitably lengthens the trajectory, yet the magnitude of this cost lacks a quantitative benchmark. This work proposes an improved ant colony optimization (IACO) method coupling free-space topological modeling with deterministic pre-planning, turning the minimum clearance from a binary compliance check into an independently schedulable planning objective. A height-constrained free space and a MAKLINK graph are built from building projections; Dijkstra supplies a deterministic initial polyline; a segment-wise clearance criterion with backward reachability is established. The node-level three-zone weight heuristic becomes a transfer-level bounded look-ahead form; and iteration deadlock is removed by a candidate-set cap with a per-ant maximum step length. Validation spans random-obstacle, public-benchmark and campus-scenario simulations. On all 56 benchmark scenarios, with the exact dynamic programming solution in the offset space as the yardstick, raising the minimum clearance from 2.5 m to 5, 11, and 20 m increases the safety margin by up to eightfold at median trajectory-length costs of only 0.05%, 0.73%, and 1.83%, and the median optimality gap against standard ACO falls from 0.740% to 0.0%. These results turn the safety margin into a budgetable “safety price list” for multi-constraint trajectory planning over dense building clusters.