How to hit a moving targetHow does a skeet shooter spot clay pigeons and shoot them down? The shooter calculates their trajectories in real time. Here's how you can calculate trajectories in embedded systems software.
Hitting a moving target can be a difficult problem. A computer program that solves this problem must recognize a moving object at one point in its trajectory, make a decision about that object, and act on that object at a later point in its trajectory. Here are some examples of this problem in applications of interest to embedded systems developers:
- widgets moving on a conveyer through an inspection station towards a push-arm that rejects sub-standard items
- a radar-detected cannon shell approaching a tank's reactive armor
- a continuous flow luggage inspection system where offending items are removed downstream
- letters zipping past address-reading devices and later being diverted into the appropriate conveyors or bins
In this article, I'll describe a programming technique for commanding an actuator to act on a ballistic object at a specific point on its trajectory. The technique assumes that the trajectory is undisturbed and that the mechanical components of the system are designed to ensure this. This technique is designed to provide accurate targeting in spite of significant, variable computational delays, such as those caused by sensor processing that is a function of the target's size or orientation. Analyses of the technique's most recent implementation show that it performs its task reliably and quickly.
Figure 1: Object-targeting model
Figure 2: Object-targeting algorithm design
Figure 3: Object-targeting data structures
Figure 1 defines the key variables of the actuator-vs.-ballistic object problem and illustrates their relationships. A target object travels at constant velocity over a fixed distance to the point at which the actuator does its work. From t0 until t1, the system captures and analyzes the target object data. If the analysis calls for action, the system's software issues the action command at t2, allowing the actuator time to respond precisely at t3. Or, in terms of the system clock, the system spends R cycles recognizing and analyzing the target object (beginning at the clock cycle whose index is r0), then delays D cycles before issuing the action command which takes A cycles to affect the target object.
When R is constant, the problem is simple. When R is a function of the object being targeted, the program must accurately measure R and then accurately calculate D. The equations that describe the problem are:
R = r1 - r0 (Equation 1a)
D = T - R - A (Equation 1b)
This problem statement includes four assumptions:
- the object velocity is constant
- the total travel distance is known
- the actuator delay period is well known (and, preferably, constant)
- each clock cycle has a unique index value
A design solution
The program design based on the object-targeting concept requires, more than anything, an accurate measure of elapsed time. The system clock illustrated in Figures 1 and 2 is the basis for measuring elapsed time in terms of clock cycles. This design assumes that the clock increments a counter to provide a unique index for each clock cycle. Not only is the current value of this cycle index, r1, made globally available to the control program; but also, when each object is first noticed, the then current cycle index, r0, is stored in the data structure for that object.
With this timing infrastructure in place, the control program can quickly and simply compute the number of clock cycles that have elapsed since the object was recognized:
R = r1 - r0
Also, the control program can solve the object targeting equation for D, the number of clock cycles from the cycle during which this calculation is being done until the cycle during which the command will be issued.
D = T - R - A
Figure 3 defines the data structures required to support the design solution. The central data structure is a command-sequencing array that stores ready-to-send commands in the order in which they're to be sent. The minimal set of information that the columnar elements of this array must hold consists of an application-specific command value and a flag indicating whether the command value is waiting to be sent. Elements of the array are selected as a function of the current clock-cycle index. As the following equation indicates, the selection is done so that the array is treated as a circular queue with M elements.
Command Index = (Current Clock Cycle Index) mod M (Equation 2)
Command-sequencing array elements are accessed for either of two reasons:
- to retrieve commands to be sent in the current clock cycle, or
- to schedule commands to be sent in a later clock cycle
Figure 2 illustrates the outline of a main/interrupt service routine (ISR)-style algorithm that makes use of the Figure 3 data structures. On the rising edge of each cycle, ISR0 is executed. It retrieves the current clock-cycle index, computes the corresponding command-sequencing array index, and retrieves the selected command information. ISR0 tests the retrieved command-waiting flag; if the flag is set, ISR0 sends the command value to the actuator. ISR0 then resets the command-waiting flag and clears the command value that's been sent. Finally, ISR0 raises a software interrupt to which ISR1 responds.
ISR1 dequeues pending command data and computes the corresponding delay values, D. ISR1 then determines the command value to be sent based on the command data. The routine inserts that value into the command-sequencing array D elements ahead of the one that corresponds to the current clock cycle; see element i+D in Figure 3. Finally, ISR1 sets that newly scheduled element's command-waiting flag. Eventually, the newly scheduled element becomes the current element, and ISR0 handles it as I described earlier.
I've just presented you with a generalized but bare-bones description of a technique for targeting a ballistic target. Here are a number of additional issues that you should consider.
The object-specific clock-cycle index, r0, is associated with a particular physical location on that object. In Figure 1, r0 identifies the leading edge of the object. Depending on the application, other assignments may be more appropriate.
The system clock period should be small enough to allow an acceptable resolution to target the object. If the actuator must affect a specific portion of an object (for instance, the first third of an object must be hit to cause it to rotate), then the system clock period must be small enough to ensure correct command placement; in the example of actuator acting on a ballistic target, the object's size in clock cycles should be at least three times the actuator's on-off cycle count.
Both object-interior targeting and action distribution are handled with modifications to the object-targeting equation. For example, to target the center of an object that extends over L clock cycles and whose r0 value is attached to the object's leading edge, you can use the following equations:
R = (r1 - r0) - L/2 (Equation 3)
And, as before:
D = T - R - A
The target will be hit when its center passes the actuator and will continue to be hit for as many clock cycles as the actuator remains on.
As I've presented it, this design solution turns actuators on but not off; it assumes the actuators turn themselves off after a known period. This doesn't have to be; you could sequence "off" commands just as well as "on" commands. However, this doubles the required command channel bandwidth. The object-targeting equation (Equation 1) assumes that an actuator's reaction time, A, is constant.
The time required to transmit a command to the actuator should be much less than the system clock period. Moving commands via direct memory access has proven to be more than adequate.
The object-targeting equation (Equation 1) doesn't account for any dynamics in the object's motion. This technique assumes that the physical components of the system work to control the object's motion.
The design solution I've presented here describes part of a control program; that program ran on a multiprocessor system. The processors were 32-bit Analog Devices DSPs; and, with the exception of clock generation and the storage of clock-cycle indices in object-data structures, a more robust form of all the described functions ran on a single DSP. I wrote the control program in assembly language and C.
Before ending this discussion, I'll share a few coding details and caveats.
The form of the commands is application-specific. A command could fit in a bit, but a byte might do, or maybe a full word is required. Whatever the case, each element of the command-sequencing array must accommodate several commands. Why? If several similar objects are detected simultaneously, the object- targeting equation (Equation 1) may assign their commands to the same clock cycle. If the command sequencing array element exceeds its capacity, the program has to handle the equivalent of a hash table collision. You can handle such collisions by placing extra commands in the very next element, or the one after that. According to the object-targeting equation, the command will be late, but that's better than not sending the command at all.
You can implement a command-sequencing array element as a C structure of the following form:
If bits or bytes are packed into the iCommand member, the bit/byte counter helps keep track of the next available command position. Adding iCommand/iCommandWaiting pairs can increase the element's capacity. The bit/byte counter, if used, spans as many iCommand members as are declared.
How many elements, M, should the command-sequencing array have? There should be at least as many elements as the maximum delay calculated by the object-targeting equation (Equation 1). Setting M equal to T would be safer. Setting M to 2T is a conservative approach that allows for easier testing because the command index wraps less frequently.
Speaking of wrapping, here's one final tip. When computing R, it's very important to handle the wrapping of the clock-cycle indices. I have yet to find an elegant way to handle all the conditions, but failure to do so will defeat this technique.
In the end, with all the details attended to, this technique has proven to be a more than adequate solution for the problem it's designed to address.
Sam Denard is a consulting software engineer who teaches and helps companies resolve their software development issues. He has been a NASA engineer, a professor of computer science, and a radio talk show host. Contact him at Proprietor@EmpiricalProducts.com.