An Efficient Motion Strategy to Compute Expected-Time Locally Optimal Continuous Search Paths in Known Environments

In this paper we address the problem of finding time-optimal search paths in known environments. In particular, we address the problem of searching a known environment for an object whose unknown location is characterized by a known probability density function (PDF). With this formulation, the time required to find the object is a random variable induced by the choice of search path together with the PDF for the object's location. The optimization problem we consider is that of finding the path that minimizes the expected value of the time required to find the object. As the complexity of the problem precludes finding an exact optimal solution, we propose a two-level, heuristic approach to finding the optimal search path. At the top level, we use a decomposition of the workspace based on critical curves to impose a qualitative structure on the solution trajectory. At the lower level, individual segments of this trajectory are refined using local numerical optimization methods. We have implemented the algorithm and present simulation results for the particular case when the object's location is specified by the uniform PDF.     

Optimally switched linear systems

In this paper we address the problem of optimal switching for switched linear systems. The uniqueness of our approach lies in describing the switching action by multiple control inputs. This allows us to embed the switched system in a larger family of systems and apply Pontryagin’s Minimum Principle for solving the optimal control problem. This approach imposes no restriction on the switching sequence or the number of switchings. This is in contrast to search based algorithms where a fixed number of switchings is set a priori. In our approach, the optimal solution can be determined by solving the ensuing two-point boundary value problem. Results of numerical simulations are provided to support the proposed method.     

A possibilistic approach to UMTS base-station location problem

In this paper, we address the problem of planning the universal mobile telecommunication system base stations location for uplink direction. The objective is to maximize the total traffic covered and minimize the total installation cost based on data involving fuzziness. To define the cost, researchers used the current period market prices as constants. However prices may change over time. Our aim here is to deal with the imprecise and uncertain information of prices. For this we introduce a model of problem where each cost is a fuzzy variable, and then we present a decision-making model based on possibility theory. To solve the problem we propose a search algorithm based on the hybridization of genetic algorithm and local search method. To validate the proposed method some numerical examples are given.     

Autocalibration with the Minimum Number of Cameras with Known Pixel Shape

In 3D reconstruction, the recovery of the calibration parameters of the cameras is paramount since it provides metric information about the observed scene, e.g., measures of angles and ratios of distances. Autocalibration enables the estimation of the camera parameters without using a calibration device, but by enforcing simple constraints on the camera parameters. In the absence of information about the internal camera parameters such as the focal length and the principal point, the knowledge of the camera pixel shape is usually the only available constraint. Given a projective reconstruction of a rigid scene, we address the problem of the autocalibration of a minimal set of cameras with known pixel shape and otherwise arbitrarily varying intrinsic and extrinsic parameters. We propose an algorithm that only requires 5 cameras (the theoretical minimum), thus halving the number of cameras required by previous algorithms based on the same constraint. To this purpose, we introduce as our basic geometric tool the six-line conic variety (SLCV), consisting in the set of planes intersecting six given lines of 3D space in points of a conic. We show that the set of solutions of the Euclidean upgrading problem for three cameras with known pixel shape can be parameterized in a computationally efficient way. This parameterization is then used to solve autocalibration from five or more cameras, reducing the three-dimensional search space to a two-dimensional one. We provide experiments with real images showing the good performance of the technique.     

INTRACTABILITY IN THE ALLEN AND KOOMEN PLANNER

The Allen and Koomen planner is intractable in two ways: the Allen interval algebra is an intractable temporal reasoner, and the collapsing problem introduces a large branching factor in the search space for a solution plan. We define independence and dependence for networks to address both problems. Independence is used to find a decomposition of an interval network, and dependence is used to focus search when faced with the collapsing problem.     

Determining the Positive Definiteness Margin of Interval Matrices

A method for determining the positive definiteness margin of interval matrices is suggested. It is based on the use of outer interval bounds on the solution set of an interval eigenvalue problem. Three algorithms of the method are developed. It is shown that their numerical complexity is polynomial. Numerical examples illustrating the applicability of the method suggested are provided.     

Near optimal control for a class of stochastic hybrid systems

To address a computationally intractable optimal control problem for a class of stochastic hybrid systems, this paper proposes a near optimal state feedback control scheme, which is constructed by using a statistical prediction method based on approximate numerical solution that samples over the entire state space. A numerical example illustrates the potential of the approach.     

A Direct Algorithm to Compute the Switching Curve for Time-Optimal Motion of Cooperative Multi-Manipulators Moving on a Specified Path

For more than two decades it has been known that the solution to the time-optimal problem for a manipulator along a specified path is bang–bang in terms of acceleration along the path and the switching points can be found by phase plane analysis. Despite great advances, no direct method is available for finding the switching points and constructing a switching curve specially for cooperative multi-manipulator systems (CMMSs). So far, all proposed methods are based on search algorithms in which one has to: (i) search the whole phase plane to establish the boundary of the non-feasible area in which the end-effector cannot follow the path and (ii) find the critical points by numerical calculation of the slope of the non-feasible boundary. Although this search algorithm can give the solution, it is very tedious and time consuming, and the problem gets worse for CMMSs. This paper is concerned with developing a direct method to find the critical points and construction of the switching curve for non-redundant CMMSs. To this end, a rigorous study of the characteristics of the critical points and the switching curve is presented, and based on that a direct algorithm is introduced.     

Robust optimization models for project scheduling with resource availability cost

We address a project scheduling problem with resource availability cost for which the activity durations are uncertain. The problem is formulated within the robust optimization framework, where uncertainty is modeled via a set of scenarios. The proposed solution method is based on the scatter search methodology and employs advanced strategies, such as dynamic updating of the reference set, a frequency-based memory mechanism, and path relinking. A multistart heuristic was also developed and comparative results are reported. The tradeoffs for risk-averse decision makers are discussed.     

Seeking the Equilibrium Situations in Bimatrix Games

Determination of the Nash-equilibria in the bimatrix game was considered by reducing it to its equivalent nonconvex problem of optimization solved by the algorithm of global search based on the theory of global extremum for this problem. Efficiency of this method was illustrated by numerical solution of bimatrix games of sufficiently high dimensions.     

A Method for Outer Interval Solution of Linear Parametric Systems

The paper deals with the problem of determining an outer interval solution (interval enclosure of the solution set) of linear systems whose elements are affine functions of interval parameters. An iterative method for finding such a solution is suggested. A numerical example illustrating the new method is solved.     

Optimal redundancy resolution of a kinematically redundant manipulator for a cyclic task

This article proposes a method for the global optimization of redundancy over the whole task period in a kinematically redundant manipulator. The necessary conditions based on the calculus of variations for integral-type criteria result in a second-order differential equation. For a cyclic task, the boundary conditions for conservative joint motions are discussed. Then, we reformulate a two-point boundary value problem to an initial value adjustment problem and suggest a numerical search method based on the iterative optimization for providing a globally optimal solution using the gradient projection method. Since the initial joint velocity is parameterized with the number of redundancy, we only search parameter values in the parameterized space using the configuration error between the initial and final time. We show through numerical examples that multiple nonhomotopic extremal solutions satisfying periodic boundary conditions exist according to initial joint velocities for the same initial configuration. Finally, we discuss an algorithm for topological liftings of the paths and demonstrate the generality of the proposed method by considering the dynamics of a manipulator.     

有色冶金过程不确定优化方法探讨

有色冶金过程受原料来源多样、工况条件波动、生产成分变化等因素的影响,存在大量的不确定性,严重影响了冶炼生产的稳定性与可靠性.鉴于此,综述不同类型不确定性优化问题的描述方法,具体包括概率不确定优化问题、模糊不确定优化问题和区间不确定优化问题.通过分析有色冶金生产过程的特点与需求,以3种典型的有色冶金过程不确定优化问题为例,探讨不同类型的有色冶金过程不确定优化方法.针对氧化铝生料浆配料过程的概率不确定优化问题,采用基于Hammersley sequence sampling(HSS)的方法实现不确定模型的确定性转换;针对湿法炼锌除铜过程的模糊不确定优化问题,采用基于模糊规则的方法进行确定性评估;针对锌电解分时供电过程的区间不确定优化问题,采用基于min-max的方法求解鲁棒解.工业运行数据均验证了上述方法的有效性.     

An inversion method for parabolic equations based on quasireversibility

This paper is concerned with a new method to solve a linearized inverse problem for one-dimensional parabolic equations. The inverse problem seeks to recover the subsurface absorption coefficient function based on the measurements obtained at the boundary. The method considers a temporal interval during which time dependent measurements are provided. It linearizes the working equation around the system response for a background medium. It is then possible to relate the inverse problem of interest to an ill-posed boundary value problem for a differential-integral equation, whose solution is obtained by the method of quasireversibility. This approach leads to an iterative method. A number of numerical results are presented which indicate that a close estimate of the unknown function can be obtained based on the boundary measurements only.     

Modified particle swarm optimization structure approach to direction of arrival estimation

This study considers the problem of estimating the direction-of-arrival (DOA) for code-division multiple access (CDMA) signals. In this type of problem, the associated cost function of the DOA estimation is generally a computationally-expensive and highly-nonlinear optimization problem. A fast convergence of the global optimization algorithm is therefore required to attain results within a short amount of time. In this paper, we propose a new application of the modify particle swarm optimization (MPSO) structure to achieve a global optimal solution with a fast convergence rate for this type of DOA estimation problem.The MPSO uses a first-order Taylor series expansion of the objective function to address the issue of enhanced PSO search capacity for finding the global optimum leads to increased performance. The first-order Taylor series approximates the spatial scanning vector in terms of estimating deviation results in and reducing to a simple one-dimensional optimization problem and the estimating deviation has the tendency to fly toward a better search area. Thus, the estimating deviation can be used to update the velocity of the PSO. Finally, several numerical examples are presented to illustrate the design procedure and to confirm the performance of the proposed method.     

The numerical study on the unsteady flow of gas in a semi-infinite porous medium using an RBF collocation method

In this paper, we study a nonlinear two-point boundary value problem on semi-infinite interval that describes the unsteady gas equation. The solution of the mentioned ordinary differential equation (ODE) is investigated by means of the radial basis function (RBF) collocation method. The RBF reduces the solution of the above-mentioned problem to the solution of a system of algebraic equations and finds its numerical solution. To examine the accuracy and stability of the approach, we transform the mentioned problem into another nonlinear ODE which simplifies the original problem. The comparisons are made between the results of the present work and the numerical method by shooting method combined with the Runge–Kutta technique. It is found that our results agree well with those by the numerical method, which verifies the validity of the present work.     

New Genetic Algorithms Based Approaches to Continuous <Emphasis Type="Italic">p</Emphasis>-Median Problem

We proposed new genetic algorithms (GAs) to address well-known p-median problem in continuous space. Two GA approaches with different replacement procedures are developed to solve this problem. To make the approaches more efficient in finding near-optimal solution two hybrid algorithms are developed combining the new GAs and a traditional local search heuristic. The performance of the newly developed models is compared to that of the traditional alternating location-allocation heuristics by numerical simulation and it is found that the models are effective in finding optimum facility locations.     

多因素制约的迷宫问题最优解的求解算法

介绍迷宫问题及其最优解,引入多因素制约的迷宫问题。重点讨论多因素制约迷宫问题最优解的含义及基于广度优先搜索的求解算法,并通过两个实例分析如何基于广度优先搜索算法求解这类迷宫问题的最优解,并给出算法的伪代码。最后,进一步讨论和总结这类迷宫问题最优解的求解算法。     

Sequential LMI approach for the design of a BMI‐based robust observer state feedback controller with nonlinear uncertainties

This paper aims at developing a robust observer–based estimated state feedback control design method for an uncertain dynamical system that can be represented as a linear time‐invariant system connected with an integral quadratic constraint–type nonlinear uncertainty. Traditionally, in existing design methodologies, a convex semidefinite constraint is obtained at the cost of conservatism and unrealistic assumptions. This paper avoids such assumptions and formulates, the design of the robust observer state feedback controller as the feasibility problem of a bilinear matrix inequality (BMI) constraint. Unfortunately, the search for a feasible solution of a BMI constraint is an NP‐hard problem in general. The applicability of a linearization method, such as the variable change method and the congruence transformation, depends on the specific structure of the problem at hand and cannot be generalized. This paper transforms the feasibility analysis of the BMI constraint into an eigenvalue problem and applies the convex‐concave–based sequential linear matrix inequality optimization method to search for a feasible solution. Furthermore, an augmentation of the sequential linear matrix inequality algorithm to improve its numerical stability is presented. In the application part, a vehicle lateral control problem is presented to demonstrate the applicability of the proposed algorithm to a real‐world estimated state feedback control design problem and the necessity of the augmentation for numerical stability.