Autonomous aerospace vehicles have become increasingly attractive for missions where human presence is dangerous or difficult. Trajectory planning is a key enabling technology for autonomous operations. In this talk, a model of autonomous operation is first developed. The problem and challenge of, as well as requirements on, onboard trajectory generations for autonomous aerospace vehicles are discussed. After an overview of various potential solution frameworks, a discrete search strategy is developed. In this strategy, a four-dimensional search space is defined and discretized. Several basic geometric shapes and their combinations represent potential obstacles and conflicts. Mathematical conditions are developed for a trajectory segment to be outside of an obstacle or conflict. Then, the A* search technique is used to obtain trajectory solutions, in which successor points are selected that avoid obstacles and conflicts, and satisfy dynamic motion constraints of the vehicle. A linear combination of flight distance and flight time is optimized in the trajectory generation process. A heuristic function that approximates this performance index is developed for the A* search procedure. Examples will be provided that illustrate the application of the proposed method. Further improvements of the method will be discussed.