(GameDev) Introduction to Proportional Navigation (Part I) blog - blahdy

In this tutorial, I will provide a brief overview of proportional navigation family of guidance laws, but more importantly, we will go over some sample code so you get straight to trying it out in your own game. This tutorial (and accompanying demonstration video) is written using World in Conflict MW Mod. Sample codes are written in Python for MW Mod's FLINT Missile System.

History of Proportional Navigation (PN)

PN is the foundation of modern homing guidance in virtually every guided missiles in use today. The theory of PN was developed by the US Navy during World War II as desperate measures were needed to protect their ships from Japanese kamikaze attacks, and gun-based defense systems (even automated fire director controlled guns) simply did not have the range to take out the target at a safe distance, and easily became overwhelmed by saturation. Automatic homing missiles were urgently needed to defend ships at sea.

Although theory of PN was apparently known by the Germans during WW II, no applications were reported and the war shortly ended thereafter. The US Navy's experimental Lark missile was the first to implement PN, soon followed by Sparrow and the venerable AIM-9 Sidewinder after the war.

PN is cheap to implement and had demonstrated to provide effective homing guidance-- It is because PN does not require geometry information such as range to target and target speed (though it can also benefit from it), making it ideal to implement on simpler "range-denied" missiles, such as passively heat-seeking IR missiles and semi-active laser homing variants. Not only that, the theory of using Line of Sight (LOS) information to develop collision course is such a powerful concept, that virtually every advanced guidance laws used today share their ancestry lineage back to PN. If you ever see people attempting to code so-called "advanced target homing" missiles in games using quadratic equations and trigonometry, you can clearly see that they're reinventing the wheels and got some learning to do :-) PN totally laughs at, and beats out every other forms of homing guidance used by games, which integrate states by solving for what is essentially a high school geometry.

Understanding Theory of PN

PN works on the principle of "Constant Bearing Decreasing Range" (CBDR), where when two objects are heading in the same direction with no change in Line of Sight (bearing) angle, objects *will* collide. Line of Sight (LOS) is an imaginary sight-line between you and the target; when target is moving from left to right in your field of view, it is said that the LOS angle is changing from left to right. If however, you were to also run from left to right and accelerate appropriately to keep the target centered in your field of view, it is then said the rate at which LOS angle is changing (LOS rotation rate) is zero ("null"). Continuing to run with LOS rate maintained at zero will result in intercept and "lead to pursuit" collision with the object you're chasing.

Mathematically, PN is stated as follows:

Commanded Acceleration = N * Vc * LOS_Rate

N = Unitless navigation gain (constant) -- between 3 to 5
Vc = Closing Velocity (or "range closing rate")
LOS_Rate = LOS Rotation Rate

To describe this along a two-dimensional missile-target engagement geometry:

When working with PN, it is important to understand that missile's acceleration is commanded (Acmd) normal to (aka perpendicular to) the LOS, and proportional to the LOS rotation rate. LOS as stated earlier, is the sight-line between missile and the target, which would be "Rtm" line in the above diagram. LOS rotation rate is the angular rate at which the LOS line changes -- denoted by the over-dot theta "LOS" grey angle in the diagram above.

Prerequisites

Before we get started, we first assume that you already have very basic knowledge in implementation of homing missiles in game. If you are this far, you probably know that in order for your game physics to work, you need some sort of integration scheme (i.e Euler, Verlet, Runge-Kutta 4, etc) that provides step-by-step numerical integration at every frame. FLINT missile system in WiC MW uses Velocity-Verlet, but essentially, what it all comes down to is simple: you step forward one step (or frame) at a time and solve for your states. If you need help with game physics and integrators, check out Gafferongames.com

Implementing PN in Game

Now, to implement PN, we need to fill in the blanks from the above equation "An = N * Vc * LOS_Rate." Let's discuss how to obtain the individual input variables to calculate our required lateral acceleration (latax).

1. Obtaining the LOS Rotation Rate (LOS_Rate)

As explained above; LOS Rotation Rate is the rate at which target is crossing your field of view, or more exactly, the rate at which sight-line angle is changing.

Obtaining LOS_Rate is easy, especially in game environment. In real life, the missile seeker sits on a gimbaled gyro -- the seeker rotates in the gyro to keep the target locked on; the rate at which it rotates is your LOS rate. In real life, engineers have to contend with seeker noise contamination, but in games, we're essentially working in a noise-free environment.

First, you need to obtain the directional vector between the missile and the target (remember "Rtm" in the above diagram?) -- this is your LOS:

RTM_new = math.Vector3( targetPosition ) - math.Vector3( missilePosition )

You will measure and record LOS at every frame; you need to now get the difference between the new RTM (RTM_new) you just measured, and the LOS obtained from the previous frame (RTM_old) -- this is your change in LOS (LOS_Delta).

RTM_new.Normalize()
RTM_old.Normalize()
LOS_Delta = ( RTM_new - RTM_old )
LOS_Rate = LOS_Delta.VectorLength()

2. Closing Velocity (Vc)

Closing Velocity (Vc) is the rate at which the missile and the target are closing onto one another. In other words, as the missile is traveling toward its target, it gets closer to the target, no? So, the rate at which our missile is closing the distance to its target is called the "range closing rate" or simply "closing velocity." This range rate is mathematically defined as follows:

Vc = -Rtm_overdot

-Rtm_overdot = Negative rate of change of the distance from the missile to the target.

Now, this raises a curious question: How do you obtain 'range rate' on a passive heat-seeking missiles that have no radar to measure distance? Well, you guesstimate it (lol) -- that's what the early rudimentary version of Sidewinder in 1953 did. Doesn't work very well against accelerating or maneuvering targets, but it was effective enough for what was world's first PN heat-seeking missile. In modern versions like the AIM-9L, AIM-9X, Stinger etc, you have computation power available in the seeker to "process" the intensity of IR or the image it sees. As IR signature gets closer, it gets more intense -- the rate of intensity change is your range closing rate.

On radar guided missiles, including semi-active homers like the original Sparrow missile, you have better luck! On a radio-frequency based sensor, the seeker can observe Doppler frequency of the target return to calculate the rate at which the missile is closing onto its target. Doppler effect is quite measurable on wavelengths as you get closer or away from the target. Negative rate of change in Doppler frequency is the closing velocity.

Anyway, now let's back to our in-game code. Recall from earlier that we derived our LOS_Rate in vector space as the difference between the current frame's missile-target vector (RTM_new) and the previous frame's missile-target vector (RTM_old). The length of the vector for this difference is denoted as LOS_Rate above. Well, just so it happens, as our missile is closing onto the target, RTM_new is shorter than RTM_old! So LOS_Rate length itself is a rate of change in missile-target distance. Then, conversely speaking, the negative rate of this distance change is our range closing rate, aka the closing velocity:

Vc = -LOS_Rate

3. Navigation Gain (N)

Navigation gain (or navigation constant) is a designer-chosen unitless variable usually in the range of 3 to 5. Higher the N, the faster your missile will null out heading errors. Generally, it is recommended for N to stay between 3 to 5. FLINT missiles in WiC MW use N of 3; most missiles in real-life use 3 as well.

4. Augmented Proportional Navigation (APN)

When implementing PN, it is best practice to focus on target's acceleration normal to LOS'-- we're using a missile to hit a moving target after all. What does 'acceleration normal to LOS' mean exactly? Well, as the missile is homing onto the target, the target would most likely move laterally, or 'perpendicular to' along the LOS sight-line (crossing target would present the most movement normal to LOS).

The reality is that, often times the target is not moving at a constant velocity -- it changes directions, or it slows down or accelerates. You also have upward sensible acceleration of 1 G even for non-maneuvering targets if you're simulating gravity.

To account for these factors, you add a term to our PN formula by adding "(N * Nt ) / 2":

Commanded Acceleration = N * Vc * LOS_Rate  + ( N * Nt ) / 2

Nt = Target acceleration (estimated) normal to LOS

Even for targets that do not maneuver, the target's one-g sensible acceleration is multiplied by N/2, producing a more efficient intercept.

Putting it all together - Sample Code

Below is a sample FLINT missile system code for FIM-92 Stinger heat-seeking missile, written in Python. It is the simplest missile in game to employ augmented PN, as it's a passive heat-seeking missile.

def GCFLINT_Lib_APN( msl_pos, tgt_pos, msl_pos_previous, tgt_pos_previous, latax, N = None, Nt = None ):
	"""
	Augmented Proportional Navigation (APN)
	A_cmd = N * Vc * LOS_Rate + N * Nt / 2
	
	msl_pos:	Missile's new position this frame.
	tgt_ps:		Target's new position this frame.
	
	msl_pos_previous:  Mutable object for missile's position previous frame.
	tgt_pos_previous:  Mutable object for target's position previous frame.
	Set these objects to "0" during first time initialization, as we haven't
	yet started recording previous positions yet.
	
	latax:	Mutable object for returning guidance command.
	N:		(float, optional) Navigation gain (3.0 to 5.0)
	Nt:		(float, optional) Target acceleration amount normal to LOS
	"""
	
	import wic.common.math as math
	from predictorFCS_flint_includes import *
	from predictorFCS_EXFLINT import *
	
	if N is None:
		# navigation constant
		N = 3.0
	else isinstance(N, float) is not True:
		raise TypeError("N must be float")
	
	if Nt is None:
		# one-g sensible acceleration
		Nt = 9.8 * EXFLINT_TICKTOCK
	else isinstance(Nt, float) is not True:
		raise TypeError("Nt must be float")
	
	if msl_pos_previous is not 0 and tgt_pos_previous is not 0:
		
		# Get msl-target distances of previous frame and new frame (Rtm)
		RTM_old = ( math.Vector3( tgt_pos_previous ) - msl_pos_previous )
		RTM_new = ( math.Vector3( tgt_pos ) - msl_pos )
		
		# normalize RTM vectors
		RTM_new.NormalizeSafe()
		RTM_old.NormalizeSafe()
		
		if RTM_old.Length() is 0:
			LOS_Delta = math.Vector3( 0, 0, 0 )
			LOS_Rate = 0.0
		else:
			LOS_Delta = math.Vector3( RTM_new ) - RTM_old
			LOS_Rate = LOS_Delta.VectorLength()
		
		# range closing rate
		Vc = -LOS_Rate
		
		# Now, calculate the final lateral acceleration required for our missile
		# to home into our target.
		latax = RTM_new * N * Vc * LOS_Rate + LOS_Delta * Nt * ( 0.5 * N )
	
	# Update mutable position objects so we can integrate forward to next frame.
	msl_pos_previous = math.Vector3( msl_pos )
	tgt_pos_previous = math.Vector3( tgt_pos )
	
	# my job is done, it's now up to EXFLINT.Integrate() to steer the missile.
	return True
		

Video Demonstration and Wrapping it All Together

The augmented PN (APN) formula above should always be used for any moving targets-- even non-maneuvering aircraft should have upward one-g sensible acceleration in a proper simulation environment, necessitating the need for APN.

The advantage of using APN guidance as compared to classic PN is that the commanded lateral acceleration (latax) is initially high but falls as the missile approaches the maneuvering target. Watch the YouTube video accompanying this blog post very closely-- you'll see that APN guided missile initially makes very violent maneuver to snap itself onto the collision path, then only minor adjustments are made just prior to missile impact. This is how optimal PN is implemented in the real world and how it should be done in realistic combat simulation games.

In the next (near future) tutorial, we will go over advanced guidance laws using theories of optimal control, which are derivatives of PN with more engagement information fed in, such as estimated time-to-intercept; and missile-target range. Feel free to message me on ModDB or YouTube if you have any questions or comments about implementing PN in your game environment.

YouTube HD Link: youtu.be/Osb7anMm1AY