Convergence analysis and validation of low cost distance metrics for computational cost reduction of the Iterative Closest Point algorithm

The Iterative Closest Point algorithm (ICP) is commonly used in engineering applications to solve the rigid registration problem of partially overlapped point sets which are pre-aligned with a coarse estimate of their relative positions. This iterative algorithm is applied in many areas such as the medicine for volumetric reconstruction of tomography data, in robotics to reconstruct surfaces or scenes using range sensor information, in industrial systems for quality control of manufactured objects or even in biology to study the structure and folding of proteins. One of the algorithm’s main problems is its high computational complexity (quadratic in the number of points with the non-optimized original variant) in a context where high density point sets, acquired by high resolution scanners, are processed. Many variants have been proposed in the literature whose goal is the performance improvement either by reducing the number of points or the required iterations or even enhancing the complexity of the most expensive phase: the closest neighbor search. In spite of decreasing its complexity, some of the variants tend to have a negative impact on the final registration precision or the convergence domain thus limiting the possible application scenarios. The goal of this work is the improvement of the algorithm’s computational cost so that a wider range of computationally demanding problems from among the ones described before can be addressed. For that purpose, an experimental and mathematical convergence analysis and validation of point-to-point distance metrics has been performed taking into account those distances with lower computational cost than the Euclidean one, which is used as the de facto standard for the algorithm’s implementations in the literature. In that analysis, the functioning of the algorithm in diverse topological spaces, characterized by different metrics, has been studied to check the convergence, efficacy and cost of the method in order to determine the one which offers the best results. Given that the distance calculation represents a significant part of the whole set of computations performed by the algorithm, it is expected that any reduction of that operation affects significantly and positively the overall performance of the method. As a result, a performance improvement has been achieved by the application of those reduced cost metrics whose quality in terms of convergence and error has been analyzed and validated experimentally as comparable with respect to the Euclidean distance using a heterogeneous set of objects, scenarios and initial situations.

Using interior point algorithms for the solution of linear programs with special structural features

Linear Programming (LP) is a powerful decision making tool extensively used in various economic and engineering activities. In the early stages the success of LP was mainly due to the efficiency of the simplex method. After the appearance of Karmarkar's paper, the focus of most research was shifted to the field of interior point methods. The present work is concerned with investigating and efficiently implementing the latest techniques in this field taking sparsity into account. The performance of these implementations on different classes of LP problems is reported here. The preconditional conjugate gradient method is one of the most powerful tools for the solution of the least square problem, present in every iteration of all interior point methods. The effect of using different preconditioners on a range of problems with various condition numbers is presented. Decomposition algorithms has been one of the main fields of research in linear programming over the last few years. After reviewing the latest decomposition techniques, three promising methods were chosen the implemented. Sparsity is again a consideration and suggestions have been included to allow improvements when solving problems with these methods. Finally, experimental results on randomly generated data are reported and compared with an interior point method. The efficient implementation of the decomposition methods considered in this study requires the solution of quadratic subproblems. A review of recent work on algorithms for convex quadratic was performed. The most promising algorithms are discussed and implemented taking sparsity into account. The related performance of these algorithms on randomly generated separable and non-separable problems is also reported.

Perturbed Proximal Point Algorithm with Nonquadratic Kernel

Let H be a real Hilbert space and T be a maximal monotone operator on H. A well-known algorithm, developed by R. T. Rockafellar [16], for solving the problem (P) ”To find x ∈ H such that 0 ∈ T x” is the proximal point algorithm. Several generalizations have been considered by several authors: introduction of a perturbation, introduction of a variable metric in the perturbed algorithm, introduction of a pseudo-metric in place of the classical regularization, . . . We summarize some of these extensions by taking simultaneously into account a pseudo-metric as regularization and a perturbation in an inexact version of the algorithm.

Optimal planning of electric-vehicle charging stations in distribution systems

With the progressive exhaustion of fossil energy and the enhanced awareness of environmental protection, more attention is being paid to electric vehicles (EVs). Inappropriate siting and sizing of EV charging stations could have negative effects on the development of EVs, the layout of the city traffic network, and the convenience of EVs' drivers, and lead to an increase in network losses and a degradation in voltage profiles at some nodes. Given this background, the optimal sites of EV charging stations are first identified by a two-step screening method with environmental factors and service radius of EV charging stations considered. Then, a mathematical model for the optimal sizing of EV charging stations is developed with the minimization of total cost associated with EV charging stations to be planned as the objective function and solved by a modified primal-dual interior point algorithm (MPDIPA). Finally, simulation results of the IEEE 123-node test feeder have demonstrated that the developed model and method cannot only attain the reasonable planning scheme of EV charging stations, but also reduce the network loss and improve the voltage profile.

Predictive control for spacecraft rendezvous in an elliptical orbit using an FPGA

A field programmable gate array (FPGA)-based predictive controller for a spacecraft rendezvous manoeuvre is presented. A linear time varying prediction model is used to accommodate elliptical orbits, and a variable prediction horizon is used to facilitate finite time completion of manoeuvres. The resulting constrained optimisation problems are solved using a primal dual interior point algorithm. The majority of the computational demand is in solving a set of linear equations at each iteration of this algorithm. To accelerate this operation, a custom circuit is implemented, using a combination of Mathworks HDL Coder and Xilinx System Generator for DSP, and used as a peripheral to a MicroBlaze soft core processor. The system is demonstrated in closed loop by linking the FPGA with a simulation of the plant dynamics running in Simulink on a PC, using Ethernet. © 2013 EUCA.

Field programmable gate array based predictive control system for spacecraft rendezvous in elliptical orbits

Copyright © 2014 John Wiley & Sons, Ltd. Copyright © 2014 John Wiley & Sons, Ltd. Summary A field programmable gate array (FPGA) based model predictive controller for two phases of spacecraft rendezvous is presented. Linear time-varying prediction models are used to accommodate elliptical orbits, and a variable prediction horizon is used to facilitate finite time completion of the longer range manoeuvres, whilst a fixed and receding prediction horizon is used for fine-grained tracking at close range. The resulting constrained optimisation problems are solved using a primal-dual interior point algorithm. The majority of the computational demand is in solving a system of simultaneous linear equations at each iteration of this algorithm. To accelerate these operations, a custom circuit is implemented, using a combination of Mathworks HDL Coder and Xilinx System Generator for DSP, and used as a peripheral to a MicroBlaze soft-core processor on the FPGA, on which the remainder of the system is implemented. Certain logic that can be hard-coded for fixed sized problems is implemented to be configurable online, in order to accommodate the varying problem sizes associated with the variable prediction horizon. The system is demonstrated in closed-loop by linking the FPGA with a simulation of the spacecraft dynamics running in Simulink on a PC, using Ethernet. Timing comparisons indicate that the custom implementation is substantially faster than pure embedded software-based interior point methods running on the same MicroBlaze and could be competitive with a pure custom hardware implementation.

Multi-areas optimal reactive power flow

This paper describes a method for the decentralized solution of the optimal reactive power flow (ORPF) problem in interconnected power systems. The ORPF model is solved in a decentralized framework, consisting of regions, where the transmission system operator in each area operates its system independently of the other areas, obtaining an optimal coordinated but decentralized solution. The proposed scheme is based on an augmented Lagrangian approach using the auxiliary problem principle (APP). An implementation of an interior point method is described to solve the decoupled problem in each area. The described method is successfully implemented and tested using the IEEE two area RTS 96 test system. Numerical results comparing the solutions obtained by the traditional and the proposed decentralized methods are presented for validation. ©2008 IEEE.

Uma investigação da influência do parâmetro de barreira na solução do problema de fluxo de potência ótimo

Pós-graduação em Engenharia Elétrica - FEB

Efficient heuristic algorithm used for optimal capacitor placement in distribution systems

An efficient heuristic algorithm is presented in this work in order to solve the optimal capacitor placement problem in radial distribution systems. The proposal uses the solution from the mathematical model after relaxing the integrality of the discrete variables as a strategy to identify the most attractive bus to add capacitors to each step of the heuristic algorithm. The relaxed mathematical model is a nonlinear programming problem and is solved using a specialized interior point method, The algorithm still incorporates an additional strategy of local search that enables the finding of a group of quality solutions after small alterations in the optimization strategy. Proposed solution methodology has been implemented and tested in known electric systems getting a satisfactory outcome compared with metaheuristic methods.The tests carried out in electric systems known in specialized literature reveal the satisfactory outcome of the proposed algorithm compared with metaheuristic methods. (C) 2009 Elsevier Ltd. All rights reserved.

Transmission system expansion planning by a branch-and-bound algorithm

A branch and bound (B& B) algorithm using the DC model, to solve the power system transmission expansion planning by incorporating the electrical losses in network modelling problem is presented. This is a mixed integer nonlinear programming (MINLP) problem, and in this approach, the so-called fathoming tests in the B&B algorithm were redefined and a nonlinear programming (NLP) problem is solved in each node of the B& B tree, using an interior-point method. Pseudocosts were used to manage the development of the B&B tree and to decrease its size and the processing time. There is no guarantee of convergence towards global optimisation for the MINLP problem. However, preliminary tests show that the algorithm easily converges towards the best-known solutions or to the optimal solutions for all the tested systems neglecting the electrical losses. When the electrical losses are taken into account, the solution obtained using the Garver system is better than the best one known in the literature.

Branch and bound algorithm for transmission network expansion planning using DC model

This paper presents an algorithm to solve the network transmission system expansion planning problem using the DC model which is a mixed non-linear integer programming problem. The major feature of this work is the use of a Branch-and-Bound (B&B) algorithm to directly solve mixed non-linear integer problems. An efficient interior point method is used to solve the non-linear programming problem at each node of the B&B tree. Tests with several known systems are presented to illustrate the performance of the proposed method. ©2007 IEEE.

Heuristic algorithm to solve the short term transmission network expansion planning

In this paper, a method for solving the short term transmission network expansion planning problem is presented. This is a very complex mixed integer nonlinear programming problem that presents a combinatorial explosion in the search space. In order to And a solution of excellent quality for this problem, a constructive heuristic algorithm is presented in this paper. In each step of the algorithm, a sensitivity index is used to add a circuit (transmission line or transformer) or a capacitor bank (fixed or variable) to the system. This sensitivity index is obtained solving the problem considering the numbers of circuits and capacitors banks to be added (relaxed problem), as continuous variables. The relaxed problem is a large and complex nonlinear programming and was solved through a higher order interior point method. The paper shows results of several tests that were performed using three well-known electric energy systems in order to show the possibility and the advantages of using the AC model. ©2007 IEEE.

A specialized genetic algorithm to solve the short term transmission network expansion planning

In this paper, the short term transmission network expansion planning (STTNEP) is solved through a specialized genetic algorithm (SGA). A complete AC model of the transmission network is used, which permits the formulation of an integrated power system transmission network expansion planning problem (real and reactive power planning). The characteristics of the proposed SGA to solve the STTNEP problem are detailed and an interior point method is employed to solve nonlinear programming problems during the solution steps of the SGA. Results of tests carried out with two electrical energy systems show the capabilities of the SGA and also the viability of using the AC model to solve the STTNEP problem. © 2009 IEEE.

Interior-exterior point method with global convergence strategy for solving the reactive optimal power flow problem

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

A one point shock capturing kinetic scheme for hyperbolic conservation laws

We have presented a new low dissipative kinetic scheme based on a modified Courant Splitting of the molecular velocity through a parameter φ. Conditions for the split fluxes derived based on equilibrium determine φ for a one point shock. It turns out that φ is a function of the Left and Right states to the shock and that these states should satisfy the Rankine-Hugoniot Jump condition. Hence φ is utilized in regions where the gradients are sufficiently high, and is switched to unity in smooth regions. Numerical results confirm a discrete shock structure with a single interior point when the shock is aligned with the grid.