Hybrid mixed-logical linear programming algorithm for collision-free optimal path planning

Hybrid mixed-logical linear programming algorithm for collision-free optimal path planning

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Control Theory & Applications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Methods to solve collision-free fuel-optimal path- and motion-planning problems for the reconfiguration of spacecraft formations are presented. First, the motion-planning problem is formulated as a parameter optimisation problem in which the spacecraft are represented by unrotated cubes and the trajectory followed by each spacecraft is discretised in time using cubic splines. In other words, the trajectory is parameterised by the spacecraft positions and velocities at a set of waypoints. Big-M relaxation is then used to formulate the parameter optimisation as a mixed-integer linear program (MILP) whose solution can be obtained using standard MILP solvers. Several concepts are subsequently introduced to obtain the solutions more efficiently and reliably. In particular, the concept of a sequential linear program is introduced in which a sequence of closely-related linear programs are solved until a better local minimum cannot be found without ‘bifurcation’, that is, without qualitatively changing the nature of the solution. An example of such a change is making one spacecraft move in front of an obstacle instead of behind it. To handle these bifurcation points efficiently, the concept of a feasibility MILP (FMILP) is introduced in which the following question is answered: is there a feasible solution whose objective function value is better than that of the current bifurcation point. This is achieved by simply appending a single linear constraint to the set of constraints. A bisection search can be applied to the cost using FMILPs to further speed the proposed method. The method was applied to two standard tests of motion planning with collision avoidance such as swapping (using minimum fuel and along the major diagonals) the positions of eight spacecraft located at the corners of a cube. Preliminary simulations show significant improvement in efficiency by at least one order of magnitude.


    1. 1)
      • A.E. Bryson , Y. Ho . (1975) Applied optimal control: optimization, estimation and control.
    2. 2)
      • D.E. Kirk . (1970) Optimal control theory.
    3. 3)
      • Singh, G., Hadaegh, F.: `Collision avoidance guidance for formation-flying applications', AIAA-2001-4088, Proc. AIAA Guidance, Navigation and Control Conf., 2001.
    4. 4)
      • Bikdash, M., Cetin, B., Singh, G., Hadaegh, F.: `Discretization of collision avoidance constraints by expanding in cubic splines', Proc. IEEE Conf. Control Applications, 2005, p. 177–184.
    5. 5)
      • Sultan, C., Seereeram, S., Mehra, R.K., Hadaegh, F.Y.: `Energy optimal reconfiguration for large scale formation flying', Proc. American Conf., 2004, 4, p. 2986–2991.
    6. 6)
      • J.-C. Latombe . (1991) Robot motion planning.
    7. 7)
      • O. Khatib . Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res. , 5 , 90 - 98
    8. 8)
    9. 9)
      • Richards, A., How, J.: `Mixed-integer programming for control', Proc. American Control Conf., 2005, p. 2676–2683.
    10. 10)
      • A. Richards , J. How , T. Schouwenaars , E. Feron . Spacecraft trajectory planning with avoidance constraints using mixed-integer linear programming. J. Guid. Control Dyn. , 4 , 755 - 764
    11. 11)
      • Prasanth, R.K., Boskovic, J.D., Mehra, R.K.: `Mixed-integer/LMI programs for low-level path planing', Proc. Automatic Control Conf., 2002, 1, p. 608–613, (1).
    12. 12)
      • Schouwenaars, T., Moor, B.D., Feron, E., How, J.: `Mixed integer programming for multi-vehicle path planning', Proc. European Control Conf., 2001.
    13. 13)
      • Richards, A., How, J., Schouwenaars, T., Feron, E.: `Plume avoidance maneuver planning using mixed-integer linear programming', AIAA-2001-4091, Proc. AIAA Guidance, Navigation and Control Conf. Exhibit,, 2001.
    14. 14)
      • Richards, A., How, J.: `Aircraft trajectory planning with collision avoidance using mixed-integer linear programming', Proc. American Control Conf., 2002, 3 (3), p. 1936–1941.
    15. 15)
      • Richards, A., Kuwata, Y., How, J.: `Experimental demonstrations of real-time MILP control', AIAA-2003-5802, Proc. AIAA Guidance, Navigation and Control Conf. Exhibit, 2003.
    16. 16)
      • Garcia, I., How, J.: `Trajectory optimization for satellite reconfiguration maneuvers with position and attitude constraints', Proc. American Control Conf., 2005, 2, p. 889–894 .
    17. 17)
      • I. Maros . (2003) Computational techniques of the simplex method.
    18. 18)
      • B. Krekó . (1968) Linear programming.
    19. 19)
      • C.A. Floudas . (1995) Nonlinear and mixed-integer programming: fundamentals and applications.
    20. 20)
      • Kuwata, Y., How, J.: `Three dimensional receding horizon control for UAVs', AIAA-2004-5144, Proc. AIAA Guidance, Navigation and Control Conf., 2004.
    21. 21)
      • T.H. Cormen , C.E. Leiserson , R.L. Rivest , C. Stein . (2009) Introduction to algorithms.
    22. 22)
      • J. Hooker . (2000) Logic-based methods for optimization: combining optimization and constraint satisfaction.
    23. 23)
      • Y. Kim , M. Mesbahi , F.Y. Hadaegh . Dual-spacecraft formation flying in deep space: optimal collision-free reconfigurations. J. Guid. Control Dyn. , 2 , 375 - 379
    24. 24)
      • Williams, A., Glavaski, S., Samad, T.: `Formations of formations: hierarchy and stability', Proc. American Control Conf., 2004, 4, p. 2992–2997, (4).
    25. 25)
      • P.K.C. Wang , F. Hadaegh . Coordination and control of multiple micro-spacecraft moving in formation. J. Astronaut. Sci. , 3 , 315 - 355
    26. 26)
      • B.A. Murtagh . (1981) Advanced linear programming: computation and practice.

Related content

This is a required field
Please enter a valid email address