Investigating the use of interval algebra to schedule mechanically steered multistatic radars

Abstract

The findings presented in this thesis support the hypothesis that Interval Algebra (IA), as a temporal reasoning language, should perform scheduling of sensor dwells efficiently and effectively. Scheduling of multistatic radars was identified as a promising research area, as it builds upon prior research into monostatic and bistatic radars in South Africa. The hypothesis can be validated by answering three research questions. Can IA allow a multistatic radar system to make more multistatic measurements of targets? Can IA perform as well as established multisensor scheduling techniques in terms of computational requirements? Is it possible to enhance the performance of IA by making use of parallel processing architectures? Answering the first two research questions required selecting a comparison algorithm that is already used extensively in scheduling. The Greedy Randomised Adaptive Search Procedure (GRASP) was selected as it represents two of the biggest groupings of existing scheduling algorithms. Furthermore, greedy optimisations are often preferred as they converge to optimal solutions quicker. Two scheduling scenarios were devised which made use of a binary mechanically steered surveillance radar network. One environment made use of a very simplistic model of the information fusion system; the other implemented all the details rigorously. The first environment was used to compare IA to GRASP, while the second tested a nimble IA scheduler. For both these environments Monte-Carlo simulations were used to test random target locations and motion. A novel IA algorithm that makes use of reduced point algebra was generated that allowed execution time to be reduced. Another, simpler novel contribution was an IA algorithm that ensured that radar tasks are only added to the IA network when required. Using these two techniques it was possible for IA to meet both the performance and execution time of GRASP, as allows for a richer set of constraints than required to perform multistatic scheduling. The Nimble IA Scheduler is a novel contribution which solves the realistic requirement of handling fast-moving and accelerating targets, and provides a small performance increase for the surveillance system. Answering the last research question required implementing IA on a parallel processing architecture. General-Purpose Graphical Processing Units (GP-GPUs) were selected since no published research made use these architectures and they should be well suited to solving constraint satisfaction problems. A novel parallel IA path consistency algorithm was generated in OpenCL building upon parallel versions found in the literature for supercomputers. Monte-Carlo simulations were run where both the serial and parallel versions were used to solve path consistency for randomly generated IA networks. The results for the GP-GPU identified that for large networks there was speed-up of between two to three times for consistent networks under three conditions. Firstly, the IA network must be sufficiently large to warrant copying the data to the GP-GPU. Secondly, the IA network must have a percentage of known constraints between 25% and 75%. Thirdly, the average number of IA operators should be less than 9.8. Thus, IA can provide equivalent performance to GRASP if the constraints are reduced. Given problems that require a richer set of constraints, these can easily be handled using IA. Nimble IA scheduling can provide a means to increase the multistatic measurements made and reduce those that are missed due to prediction inaccuracies. IA path consistency can also be used on GP-GPUs but only provides speed-ups under specific conditions.