2023-06-25
6-chapter book by Peter Moo and Zhen Ding [MD15].
Definitions aren’t consistent in this book, task is sometimes == look, other times not. Sometimes it’s a sensor, a radar, or a node. It’s clear it is always referencing some other work, but it is a lot for somebody coming in with no prior experience.
I’m most excited about the waveform selection. In my head, an AI that is tasked with a relatively tight set of waveform selections that is rewarded for correctly tracking targets could be an elegant, if black box, way to just step over a lot of this.
I think much of the complexity here is that they are trying to draw borders where none exist. Dynamic prioritization is trying to set the revisit rate parameters on certain tasks such that the radar doesn’t get overwhelmed, but it’s clunky and has a strange boundary at 0.75. As things get busier, they move more off, but it’s not clear they ever get promoted again. When there are multiple priorities, it seems like the ‘surveillance’ queue could just end up being never ever visited again, just because a certain number of ‘sufficiently high’ priority targets have been spotted.
Radar Resource Management (RRM) considers prioritization, scheduling, parameter selection, and optimization of radar looks and tasks.
Determine the start time or drop of each look.
Adjust:
Several tasks are associated with each function.
3 Constraints:
Each task independently sends look requests to the radar scheduler.
Radars can do:
Task prioritization, task scheduling.
Scheduling time may be improved by using waveform-aided algorithms and adaptive update rate algorithms.
A 1992 paper on adaptive waveform selection with a neural network from back when training neural networks was called “simulated annealing” combines neural networks and waveform-aided algorithms.
Classifiers for priorities.
An example is given:
Features:
Then a very ML101 description of backprop.
A 1994 paper on optimal radar pulse scheduling using a neural network by Alberto Izquierdo-Fuente and J.R. Casar-Corredera walks us through using an energy function to converge on local optima, they say it’s slow for many targets, they simulate 5 tracks on 1994 hardware.
They specifically mention that creating learning data sets is non-trivial.
Just use a LUT for task prioritization.
They claim this is fuzzy but all I see is a bog-standard decision tree. They do a bit of feature engineering bolting range, velocity, identity, and direction into a “Hostility” scalar. The threat is “the linguistic variable”? Again, sounds like feature engineering to some scalar? They then lose me with a ‘fuzzification, fuzzy rules, fuzzy logic, de-fuzzification’ for what, as far as I can tell, is just encoding Hostility, Weapon System, and Position into 3-ary and Track quality and Threat into 7-ary values and wandering down a decision tree. I’m left feeling like I’m missing something.
The Adapt_MFR has this built in and is used as a baseline.
A 2003 paper on the use of entropy for optimal radar resource management and control by Paul Berry and David Fogg uses information entropy to schedule track updates. Minimize the update rate to maximize the probability of the target being within a beam, dwell time should be maximized to get the best signal-to-noise ratio. They develop an expression to quantify the overall uncertainty associated with targets and balance resources based on this.
Moo tells us “In real applications, dynamics are unknown and therefore entropy calculation would be inaccurate”. I feel that this can’t be true, and that the correctness of predictions should be used to update certainty about each target. It’s just a hidden Markov something in the sky that is almost certainly going to be bound by physics and be, to a first-order approximation, just traveling in some ballistic arc. I think you could narrow down a pretty tight cone of possible tomorrows with just a few samples, and if you haven’t, well, that’s a higher entropy target so it needs more time.
They note 20 papers that try to do task prioritization and task scheduling simultaneously.
The example framing is still totally different from mine, in theirs each task is proposing different allocations. They give costs and performance gains. It isn’t clear to me how they deal with overloading in this case.
There is no linear formulation of theirs either.
“Implemented in the experimental MESAR system”. It’s a 90s big multi-function radar.
Sounds like the authors are skeptical about the generalizability of everything done so far.
Quality-of-Service (QoS). Q-RAM uses a concave majorant operation to reduce the number of setpoints to be considered for the broader NP-hard allocation problem.
This sounds like what I’m working on, it basically says that it uses heuristics to assign parameters to tasks after considering a variety of factors. Then there is a fast convex optimization to solve and Bob’s your uncle. For me, the parameters are just handed down from god. This confused me, and after reading this chapter, I now see I shouldn’t be using those as I have.
There’s some pretty strong chicken-and-egg going on with picking good priority levels.
Then it starts talking about high probability schedulability in ways that confuse me.
Ghosh et al. schedule a 100-task radar problem to be performed in 700 ms. No mention of hardware.
Scheduling based on semantic importance alone leads to unpredictable system behavior and poor resource utilization. Semantic is ‘targets threat level’, scheduling priority is whatever else, for example, earliest deadline first.
Sounds like Ghosh’s solution is to use semantic priorities as weights for scheduling ones, which is something that again, I’ve been doing all along just due to how I started out.
So instead of scheduling tasks, we schedule beams and waveforms. This looks like much more fun. Suvorova, Howard, et Moran. “Paranoid Tracker”, treats surveillance as just tracking some imaginary targets, this is why they call it paranoid. Cute hack, I’ll probably steal this.
Then they start talking about MIMO things building waveforms to maximize discrimination information in the echo signal. The communication community loves this stuff, it’s immature in radars. The future is on-the-fly waveform generation. Designing waveforms is hard.
These are both actually in use and very useful for obvious reasons, but they make optimization and classification of motion noise more difficult.
Three benchmark problems from NRL, simulate a array 4 GHz mono-pulse radar, 6 or 12 targets. 1994 beam-pointing problem, a 1995 extension, and a 1999 closely spaced objects problem with two additional simulated sensors. The track is considered lost if the distance between the true target position and the target position estimate exceeds 1.
Solutions with longer intervals between updates are considered better, they summarize a bunch of acronyms and numbers. Latest ones don’t have good comparisons.
Benchmark 3 is not publicly available.
Scheduler, Detector, and Tracker. Detection and tracking are the two primary multifunction radar functions.
How timely beams are scheduled?
Papers from 2014.
DRDC Ottawa tool to model naval radars.
The simulation loop moves in increments of the dwell time of the radar beam.
A decision tree to lower track priority during overloading.
An operating system like scheduling. Once a task is scheduled, it moves to the back of some queue.
Plots for the Fuzzy Logic and Time-Balancing are interlaced with some fairly terse math. There are plots showing priority going down over time. I guess they introduced a bunch of targets all just before 200 s and this shows that eventually they get siphoned off to lower priority, with no obvious impacts on a lot of things, other than just being better than ‘nonadaptive’ pretty much across the board.
This is how the chapter ends, perhaps if I spent more time thinking about it I could figure out what these plots should be telling me, but as presented, I have no idea if this is good or bad.
Two sets of priorities: 1) Function Priorities 2) Task Priorities
These are enumerated 1 through 8, given names like “1. high-priority tracks”, “5. track initiation”, and “8. built-in-test”. Curious to me that track initiation is a lower priority than track maintenance.
Time-balancing scheduler is a simple and efficient linear programming algorithm. Each function has a time balance, the function with the maximum time balance goes next.
Basically, you tweak these time budgeting functions until you get the ratios you want for the different tasks. In this case, not much at all like operating systems, the tasks are all left to run for their full duration and never release their time early or wait for interrupts. It is not clear to me what this actually solves, it feels like it just kicks the problem one step down the road to picking good time balance algorithms to keep everything properly balanced.
Decide which looks to retain by tracking error covariance to schedule track updates.
These ‘looks’ are like my ‘tasks’, but richer.
In this case, they build a ‘benefit ^’ instead of a ‘cost V’, this also means that all unscheduled tasks just have zero benefit, they can’t make dropping higher priority tasks worse, I guess they just plan to capture this in having taller benefit tents.
Input is look requests, and the output is a viable subset of looks, where , and the start times of each of the looks.
Look requests are sorted by desired start time, so are not shuffled around. Reduces search space, not necessarily optimal schedule.
It first selects a viable set, then gives start times. Given that it isn’t ever shuffling any, the start time assignment is probably pretty simple. NOTE: It is not just head-to-tail, they do some linear programming to maximize the benefit function.
The more I read the more I realize that I basically just accidentally remade a worse version of this. They’re trying to add new tasks and pick the one with the biggest benefit and keep going forever. I guess the way I could slide around multitasks is interesting.
They come up with a few corner cases that end up actually simplifying the problem. One I’ve thought of: What if the slope takes the benefit below zero before reaching the latest start time, a bizarre situation where the schedule could be improved by dropping a task would appear. I guess the iterative way they add tasks prevents this from happening.
For surveillance functions, they have a whole function to cram them in where they fit. Implementation details: It’s a bit of a generator function that just always has one outstanding look request.
Equal look priorities: looks are scheduled FIFO.
Unequal look priorities: Position in the queue is determined by some function, but yikes, this feels so complex I’m not sure why we treat it as a subsystem and don’t just schedule everybody together.
I guess there’s some concept of “Primary Looks” that are, by definition, all higher priority than any “Secondary Look”. This feels wrong to me though. If ever tracking reaches overload, we could go years without ever doing surveillance.
In this framing, the window is from 0 to approximately 300 ms, where it schedules 300 ms of tasks and whenever the last one ends is the true end. They also seem to just define a small number of looks with a clear hierarchy, then basically spam the top one until no more fit, then spam the later ones.
25 s interval. Primary looks consist of tracking looks only. 30 targets, track initialization for each target randomly between 5 and 20 s. Surveillance looks dwell 2 ms, tracking ones take 5 ms and must be updated every 150 ms.
Orman puts 56% on time, with 7% being at least 20 ms away. The proposal is always within 13 ms, but only 43% on time.
In the graph, we see that surveillance starts at 100% occupancy for the first 5 seconds, then ramps up pretty fast, until tracking is 100% of occupancy in both cases. To me, this renders both useless. If after 15 seconds you never do surveillance ever again in your life, you’ll bump into a lot of walls.
Linear programming. This feels glossed over, but seems to significantly improve performance.
They talk about using curves instead of the two slopes. Works the same.
Sensor resource management, assignment of multiple sensors to multiple tasks. They draw a line between “C2”, command and control, and “RRM”, the individual sensors scheduling things.
“Track Scheduling” by He and Chong, modified Q-RAM to minimize sensor loading.
They consider networks of monostatic radars, multistatic sounds fun though.
They consider two types, centralized management and distributed management. Without reading any further, my hunch is that centralized management is worth it based on how difficult herding cats in the systems world has proven to be.
Communication channel matters in networked radars, when wireless, it will change over time.
As far as I can tell, node == sensor == radar in this chapter.
Nodes with overlapping regions must decide which contributing node should carry out the associated task.
Distributed tracking, one of the: 1) independent tracking, each radar on its own 2) distributed track fusion, each radar on its own, tell somebody central 3) distributed track maintenance, single track for each target, measurements from all radars
A single resource manager sends schedules to all nodes. The only real downside they point out is varying communication bandwidth and maybe losses of communication. Strikes me that any distributed system will necessarily be noisier on any communication network, and therefore only suffer from this worse.
This says the advantage is reduced communication, but also that every radar talks to every other radar. Broadcasting everything everywhere has to be fatter than a scheduler-worker arrangement.
They say when overlaps exist, the contributing nodes can coordinate on some schedule.
They have a taxonomy:
They again make this big bizarre assertion that type 3 is “less computational complexity but increased overall channel throughput” as if centralization somehow increases communication.
A repeat of previous chapters on this. Decision tree.
The organization of this whole section is chaotic, they keep jumping from seemingly broad thoughts about prioritization or error correction during communication and back to algorithm-specific implementation details down to the decimal.
This is actually a 3 in 1 deal, everything we’ve seen before for single radars though.
Radars first negotiate overlaps, then only detections in overlapping regions are communicated.
Look by look, which they then just assert is more computationally expensive? I feel like I’m getting a “doing a bad job with distributed is easier than doing a good job with centralized”. Dispatching individual looks must be easier than trying to reason about big baskets of looks.
Here they use “Minimum Range” to assign each look, which is basically just slicing the overlapping regions in half. This has got to be ridiculously cheap computationally.
Basically channel is available with probability . Down below they’ll only ever set it to 1 and 0.5. Also, the way they did the intervals were in big blocks of 10 s at a time, flipping a coin every 10 s to see.
Lots of fun with Adapt_MFR, too bad I don’t think I can play with it.
Track initiation process:
They seem to think the jury is still out on this one. I’m frankly confused, it strikes me that centralized must be better in every way, and that Type 2 must be better than Type 1 if you’re serious about distributed for some reason.
“Due to this high computational complexity, optimal techniques such as dynamic programming and neural network algorithms cannot be implemented in real-time schedulers”. This statement confuses me, the whole point of dynamic programming is to make it cheap, and neural networks aren’t necessarily optimal. I also don’t think I was given any actual definition of what this “Real Time” constraint is in this problem space.
Adapting to changing environments is challenging and necessary.
Coordinated uber alles.
The objective of the radar is to detect and track all targets within its field of regard.
There is a need to establish a set of benchmark problems for RRM. NRL introduced benchmark problems for tracking that led to a number of advances in tracking. Benchmark problems for RRM would specify common radar parameters and target scenarios that enable researchers to evaluate their algorithms against a common network.
They don’t give hints on how to do this.
Big complexity, with the potential for big enhancements.