This paper presents a mathematical programming approach to online connectivity-constrained trajectory planning for autonomous helicopters through cluttered environments. A lead vehicle must execute a certain mission whereby wireless line-of-sight communication to its ground station is lost. Relay helicopters are therefore introduced that must position themselves in such a way that indirect line-of-sight connectivity between the leader and the ground station is always maintained. This requires coordinated multivehicle trajectory optimization which is tackled online using centralized and distributed receding horizon planning strategies. The problem is formulated as a mixed-integer linear program that accounts for the vehicle dynamics, obstacle and collision avoidance, and connectivity constraints. A centralized two-helicopter mission is described for which simulation, hardware in the loop, and real-time flight-test results that show the online adaptability of the approach are presented. Simulations of distributed scenarios are given as well. © 2006 Wiley Periodicals, Inc.