Network theory for efficient optimal motion planning
Cherif Ahrikencheikh · 1993
Motion Planning, Optimum Routing, and Collision Avoidance problems have attracted considerable attention in recent years because they are faced in many different areas, particularly in Robotics, Autonomous Systems, Electronic Packaging, NC Machining, Navigation, and Traffic Control. There exist many excellent research publications dealing with this general topic. Nevertheless, because of the extensive computations necessary for dealing with this type of problem in real world situations, such as planning multi-body motions in 3-dimensional space with imposed constraints on the geometry and the dynamics of the movements, none of the existing approaches consider the problem of path optimization. That is, available techniques deal mostly with finding a feasible collision-free path without concern for optimization. This research presents a new approach for dealing with this class of problems, which aims at finding optimized collision-free motions without trading off the computational efficiency. The approach is based on modeling stationary and moving objects as polytopes in spaces with two, three, or more dimensions. Polynomial-time algorithms are developed to process these polytopes and generate collision-free trajectories with optimized length or corresponding travel time. Because of using approximate polytope representations, true optimality may not be reached in some problems. Additional simplifications in the implementation of the algorithms may also result in trading off universal optimality. Nevertheless, as demonstrated by several implemented examples, the solutions obtained are either optimum or closely approach optimality. Such solutions are therefore called optimized. The algorithms presented in this thesis have the following distinct features: (1) The computational performance is a polynomial function of the complexity of the objects geometry, such as the total number of edges. (2) Optimized solutions are generated for a wide variety of problems, including the multi-body motion in 3-dimensional space. (3) Automatic compliance with given dynamic constraints, in addition to the geometric constraints or tolerances on the motion, is easily accommodated.