In this chapter, we present the fundamentals used in the analysis and design of terminal homing guidance systems. The purpose of terminal guidance is to cause a pursuer (typically a missile) to hit, or come close to, a preselected target.Moreover, we require that this interception take place despite unpredictable maneuvers of the target, disturbances, and navigation uncertainties.Here wemake a rough distinction between three types of terminal guidance: homing, ballistic, and midcourse. This distinction is based on the amount of control authority that is applied during most of the flight and does not lead to categories with sharply defined boundaries. Ballistic and midcourse guidance are studied in Chapters 6 and 7, respectively.

In homing guidance, we make the following assumptions:

1. The pursuer is actively controlled during the entirety of the engagement.

2. The pursuer has a velocity with constant norm (this is typical of the terminal phase of an engagement in atmospheric flight).

3. The pursuer is equipped with a passive seeker (e.g., a heat seeker), or a semipassive seeker (such as in laser-guided, smart bombs).

Under the preceding assumptions, we study solutions to the terminal homing guidance problem. We also allow the possibility of limiting the radius of curvature of the pursuer's trajectory.

Section 5.1 presents the fundamentals of planar homing guidance and identifies the main candidate strategies for homing.

Game theory is an extension of control theory that deals with situations where several players exercise authority over a system. In general, each player may pursue its own objective. The players are not necessarily adversaries; they may choose to cooperate if it is to their advantage. In addition, the players may not know everything there is to know. They may act to learn what they do not know, or exploit the situation based on what they do know. This is a typical exploration-exploitation trade-off.

Game theory has applications to economics (several Nobel Prizes were awarded in this field), international diplomacy, guidance and pursuit evasion, warfare, and sports. Game theory is also applicable to control (see Figure 1.4), where the exogenous and endogenous inputs are two players in a game.

Section 10.1 presents a taxonomy of two-player games. Section 10.2 describes an example of a simple game of pursuit evasion in a two-player football scrimmage. Section 10.3 describes the Bellman-Isaacs equation. Sections 10.4 and 10.5 present modeling and features of the solution for the homicidal chauffeur game. Section 10.6 describes a game-theoretic view of proportional navigation. Sections 10.7, 10.8, and 10.9 present a summary of the key results in the chapter, bibliographic notes for further reading, and homework problems, respectively.

Taxonomy of Two-Player Games

We consider two-player games, in which the two players have control actions u and v, respectively.

The next two chapters treat optimization and optimal control for the purpose of their application to guidance. Chapter 8 focuses on optimization as a stepping-stone toward optimal control, which is treated in Chapter 9. Optimization is concerned with finding the best option from among several to solve a problem.

Optimization is often necessary in aerospace engineering because of the merciless requirements that physics and chemistry impose on flying systems. For instance, it is well known that to lift 1 kg of payload from Earth's surface to orbit, using chemical rocket propulsion, it is required to use at least 80 kg of rocket structure, engine, fuel, and propellant [78]. This staggering 80/1 ratio is one of many stark reminders that, when it comes to flight, optimization is of the essence.

Throughout this chapter, we discuss necessary and sufficient conditions for optimality. Let us clarify what we mean by these. A necessary condition for optimality is a statement of the form: “If item x is optimal (i.e., is the best), then condition NC(x) must be satisfied.” Typically, condition NC(x) provides enough information to determine x. A sufficient condition for optimality is a statement of the form: “If item x satisfies condition SC(x), then item x must be optimal.” Here also, typically condition SC(x) provides enough information to determine x. In view of these statements, the following caution is in order: necessary conditions guarantee neither optimality of x, nor even existence of a solution to the optimization problem.

In this chapter, we present the theory that is used in the analysis and design of navigation systems for aerospace vehicles, with an emphasis on the fundamentals rather than on their hardware implementation. The purpose of navigation is twofold: to estimate the position and velocity of a vehicle based on the output of imperfect sensors and to assess the accuracy of these estimates. Mathematically, this corresponds to computing the first and second moments (expected value and covariance) of a particular random variable. Note that one should not neglect the importance of the accuracy assessment. Indeed, for a vehicle traveling in the vicinity of Earth, the question “Where is the vehicle?” can always be answered by “On the Sun, to within one light-hour.” (Recall that the Earth is 8 light-minutes away from the Sun.) Such an answer, although it is correct, is totally useless for guiding the vehicle in the vicinity of the Earth. It is therefore very important to quantify the navigation error.

We start, in Section 4.1, by considering the navigation problem under the most restrictive assumptions: perfect sensors, nonredundant measurements, static estimation, nonrecursive processing, and perfect clock. Then, in subsequent sections, we remove these assumptions sequentially to build up the theory. Specifically, Section 4.2 considers position fixing with imperfect, nonredundant measurements, and Section 4.3 treats the case of imperfect redundant measurements.

In this chapter, we present the fundamentals used in the analysis and design of midcourse guidance systems. These systems are predicated on the following assumptions:

1. In mission planning, a set of nominal trajectories that meet mission specifications is determined.

2. During flight, corrections are continually applied to the trajectory to return it to nominal. This sustained application of control authority is the distinguishing feature of midcourse guidance.

We consider three methods for midcourse guidance. In the first method, the set of nominal trajectories is parametrized by initial position and initial time, which specify the required velocity. This leads to the formalism of velocity-to-be-gained guidance, also known as Q-guidance. In the second method, a single nominal trajectory is determined and control is applied to return the trajectory to it. This leads to the formalism of state feedback guidance, also known as Delta-guidance. The third method combines state feedback guidance with navigation in that it uses Delta-guidance based on an estimate of the state vector rather than the true state vector.

Midcourse guidance is related to work presented in the previous two chapters. Indeed, in Chapter 5, the primary purpose of homing is to come close to a target - in other words, homing is a “final-value” problem. However, constant bearing guidance can be viewed as a form of midcourse guidance where the nominal trajectory is defined by β = 0.

This chapter presents the elements of stochastic systems theory that we use in the analysis and synthesis of navigation and guidance systems. Roughly speaking, a stochastic phenomenon is randomly unpredictable but exhibits “statistical regularity,” in a sense defined subsequently. Consistent with our emphasis on linear systems, justified in Chapter 2, the purpose of this chapter is to quantify how linear systems respond to uncertain input signals.

We use stochastic models to account for uncertainty for at least two compelling reasons. The first one is purely pragmatic: stochastic models have proven extremely effective in modeling uncertainty in science and engineering and provide a rational basis for taking and optimizing decisions in the presence of the unknown. The second, deeper reason, appeals to the fundamental postulate of natural science [24], which states that “nature is governed by laws that are uniform.” Although this postulate leads us to expect that natural phenomena be highly and exactly repeatable, the uncertainty we observe in practice seems to violate this expectation. A way to resolve this dilemma is to relax the notion of exact repeatability into that of statistical regularity, leading seamlessly to stochastic systems theory. Hence stochastic systems theory affords a provision for uncertainty within the context of the fundamental postulate of natural science.

The motivation of this chapter is that many phenomena in navigation and guidance can be modeled as stochastic. They include measurement errors in components of acceleration, velocity and position, drift of gyroscopes, wind gusts, and so on, and the navigation and guidance errors that the aforementioned generate.

Desire to improve drives many human activities. Optimization can be seen as a means for identifying better solutions by utilizing a scientific and mathematical approach. In addition to its widespread applications, optimization is an amazing subject with very strong connections to many other subjects and deep interactions with many aspects of computation and theory. The main goal of this textbook is to provide an attractive, modern, and accessible route to learning the fundamental ideas in optimization for a large group of students with varying backgrounds and abilities. The only background required for the textbook is a first-year linear algebra course (some readers may even be ready immediately after finishing high school). However, a course based on this book can serve as a header course for all optimization courses. As a result, an important goal is to ensure that the students who successfully complete the course are able to proceed to more advanced optimization courses.

Another goal of ours was to create a textbook that could be used by a large group of instructors, possibly under many different circumstances. To a degree, we tested this over a four-year period. Including the three of us, 12 instructors used the drafts of the book for two different courses. Students in various programs (majors), including accounting, business, software engineering, statistics, actuarial science, operations research, applied mathematics, pure mathematics, computational mathematics, computer science, combinatorics and optimization, have taken these courses. We believe that the book will be suitable for a wide range of students (mathematics, mathematical sciences including computer science, engineering including software engineering, and economics).

In Chapter 2, we have seen how to solve LPs using the simplex algorithm, an algorithm that is still widely used in practice. In Chapter 3, we discussed efficient algorithms to solve the special class of IPs describing the shortest path problem and the minimum cost perfect matching problem in bipartite graphs. In both these examples, it is sufficient to solve the LP relaxation of the problem.

Integer programming is widely believed to be a difficult problem (see Appendix A). Nonetheless, we will present algorithms that are guaranteed to solve IPs in finite time. The drawback of these algorithms is that the running time may be exponential in the worst case. However, they can be quite fast for many instances, and are capable of solving many large-scale, real-life problems.

These algorithms follow two general strategies. The first attempts to reduce IPs to LPs – this is known as the cutting plane approach and will be described in Section 6.2. The other strategy is a divide and conquer approach and is known as branch and bound and will be discussed in Section 6.3. In practice, both strategies are combined under the heading of branch and cut. This remains the preferred approach for all general purpose commercial codes.

In this chapter, in the interest of simplicity we will restrict our attention to pure IPs where all the variables are required to be integer. The theory developed here extends to mixed IPs where only some of the variables are required to be integer, but the material is beyond the scope of this book.

Possible outcomes

Consider an LP (P) with variables x1, …, xn. Recall that an assignment of values to each of x1, …, xn is a feasible solution if the constraints of (P) are satisfied. We can view a feasible solution to (P) as a vector x = (x1, …, xn)T. Given a vector x, by the value of x we mean the value of the objective function of (P) for x. Suppose (P) is a maximization problem. Then recall that we call a vector x an optimal solution if it is a feasible solution and no feasible solution has larger value. The value of the optimal solution is the optimal value. By definition, an LP has only one optimal value; however, it may have many optimal solutions. When solving an LP, we will be satisfied with finding any optimal solution. Suppose (P) is a minimization problem. Then a vector x is an optimal solution if it is a feasible solution and no feasible solution has smaller value.

If an LP (P) has a feasible solution, then it is said to be feasible, otherwise it is infeasible. Suppose (P) is a maximization problem and for every real number α there is a feasible solution to (P) which has value greater than α, then we say that (P) is unbounded. In other words, (P) is unbounded if we can find feasible solutions of arbitrarily high value. Suppose (P) is a minimization problem and for every real number α there is a feasible solution to (P) which has value smaller than α, then we say that (P) is unbounded.

In this chapter, we revisit the shortest path and minimum-cost matching problems. Both were first introduced in Chapter 1, where we discussed practical example applications. We further showed that these problems can be expressed as IPs. The focus in this chapter will be on solving instances of the shortest path and matching problems. Our starting point will be to use the IP formulation we introduced in Section 1.5. We will show that studying the two problems through the lens of linear programming duality will allow us to design efficient algorithms. We develop this theory further in Chapter 4.

The shortest path problem

Recall the shortest path problem from Section 1.4.1. We are given a graph G = (V, E), nonnegative lengths ce for all edges e ∈ E, and two distinct vertices s, t ∈ V. The length c(P) of a path P is the sum of the length of its edges, i.e. Σ(ce: e ∈ P). We wish to find among all possible st-paths one that is of minimum length.

Example 7 In the following figure, we show an instance of this problem. Each of the edges in the graph is labeled by its length. The thick black edges in the graph form an st-path P = sa, ac, cb, bt of total length 3 + 1 + 2 + 1 = 7. This st-path is of minimum length, hence is a solution to our problem.