In this thesis, we introduce a new class of problems, which we call Optimal Areal Positioning (OAP), and study a special form of these problems. OAPs have important applications in earth observation satellite management, tele-robotics, multi-camera control, and surveillance. In OAP, we would like to find the optimal position of a set of floating geometric objects (targets) on a two-dimensional plane to (partially) cover another set of fixed geometric objects (requests) in order to maximize the total reward obtained from covered parts of requests. In this thesis, we consider the special form of OAP in which targets and requests are parallel axes rectangles and targets are of equal size. A predetermined reward is associated with covering an area unit of each request. Based on the number of target rectangles, we classify rectangular OAP into two categories: Single Target Problem (STP) and Multi-Target Problem (MTP). The structure of MTP can be compared to the planar p-center which is NP-complete, if p is part of the input. In fact, we conjecture that MTP is NP-complete. The existing literature does not contain any work on MTP. The research contributions of this thesis are as follows: We develop new theoretical properties for the solution of STP and devised a new solution approach for it. This approach is based on a novel branch-and-bound (BB) algorithm devised over a reduced solution space. Branching is done using a clustering scheme. Our computational results show that in many cases our approach significantly outperforms the existing Plateau Vertex Traversal and brute force algorithms, especially for problems with many requests appearing in clusters over a large region. We perform a theoretical study of MTP for the first time and prove several theoretical properties for its solution. We have introduced a reduced solution space using these properties. We present the first exact algorithm to solve MTP. This algorithm has a branch-and-bound framework. The reduced solution space calls for a novel branching strategy for MTP. The algorithm has a main branch-and-bound tree with a special structure along with two trees (one for each axis) to store the information required for branching in the main tree in an efficient format. Branching is done using a clustering scheme. We perform computational experiments to evaluate the performance of our algorithm. Our algorithm solves relatively large instances of MTP in a short time.

Thesis (MEng)--Stellenbosch University, 2015. / ENGLISH ABSTRACT: The ability of satellites to actively control their attitude has changed the way we live. Navigation systems, satellite television, and weather forecasting, for example, all rely on satellites which are able to determine and control their attitude accurately. This project was aimed at designing and analysing an attitude determination and control system (ADCS) for a 20 kg Earth observation satellite by means of simulation. A realistic simulation toolset, which includes the space environment, sensor, and actuator models, was created using MATLAB and Simulink. An ADCS hardware suite was selected for the satellite based on a given set of pointing and stability requirements, as well as current trends in the small satellite industry. The hardware suite consists of among others a star tracker and three reaction wheels. A variety of estimators and controllers were investigated, after which an application specific ADCS state machine was defined. The state machine included a Safe Mode for de-tumbling, a Nominal Mode for normal operation, a Forward Motion Compensation (FMC) Imaging Mode for Earth observation, and a Target Tracking Mode for ground station tracking. Simulation results indicated that de-tumbling, coarse and fine sun tracking, FMC factor 4 imaging, and target tracking were successfully implemented. Lastly, the satellite’s pointing error and stability were determined to be less than 70 arcseconds and 7 arcseconds per second respectively, both values well within the given requirements. / AFRIKAANSE OPSOMMING: Satelliete se vermoë om hul oriëntasie aktief te beheer, het die manier waarop ons lewe, verander. Navigasiestelsels, satelliettelevisie en weervoorspelling, byvoorbeeld, maak staat op satelliete wat hul oriëntasie akkuraat kan bepaal en beheer. Die mikpunt van hierdie projek was die ontwerp en analise van ’n oriëntasiebepaling- en -beheerstelsel (ADCS) vir ’n 20 kg aardwaarnemingsatelliet deur middel van simulasie. ’n Realistiese simulasieopstelling, wat modelle van die ruimteomgewing, sensore en aktueerders insluit, was ontwikkel deur gebruik te maak van MATLAB en Simulink. ’n ADCS hardewarestel was gekies vir die satelliet op grond van ’n stel rig- en stabiliteitsvereistes, sowel as die huidige tendense in die klein-satellietbedryf. Die hardewarestel bestaan onder andere uit ’n stervolger en drie reaksiewiele. Nadat verskeie afskatters en beheerders ondersoek was, was ’n toepassingspesifieke ADCS toestandmasjien gedefinieer. Die toestandmasjien het ’n Veilige Modus vir onttuimelling, ’n Nominale Modus vir normale operasie, ’n Vorentoe-bewegingskompensering (FMC) Beeldskandeermodus vir aardwaarneming en ’n Teikenvolgmodus vir grondstasie volging ingesluit. Simulasieresultate het aangedui dat onttuimeling, growwe- en fyn sonvolging, FMC faktor 4 beeldskandering en teikenvolging suksesvol geïmplementeer was. Laastens was die satelliet se rigfout en stabiliteit bepaal as minder as 70 boogsekondes en 7 boogsekondes per sekonde onderskeidelik, albei waardes gemaklik binne die vereistes.