On the Accuracy of the MAP Inference in HMMs

In a hidden Markov model, the underlying Markov chain is usually unobserved. Often, the state path with maximum posterior probability (Viterbi path) is used as its estimate. Although having the biggest posterior probability, the Viterbi path can behave very atypically by passing states of low marginal posterior probability. To avoid such situations, the Viterbi path can be modified to bypass such states. In this article, an iterative procedure for improving the Viterbi path in such a way is proposed and studied. The iterative approach is compared with a simple batch approach where a number of states with low probability are all replaced at the same time. It can be seen that the iterative way of adjusting the Viterbi state path is more efficient and it has several advantages over the batch approach. The same iterative algorithm for improving the Viterbi path can be used when it is possible to reveal some hidden states and estimating the unobserved state sequence can be considered as an active learning task. The batch approach as well as the iterative approach are based on classification probabilities of the Viterbi path. Classification probabilities play an important role in determining a suitable value for the threshold parameter used in both algorithms. Therefore, properties of classification probabilities under different conditions on the model parameters are studied.     

Mathematical modeling and trajectory planning of mobile manipulators with flexible links and joints

This paper is concerned with mathematical modeling and optimal motion designing of flexible mobile manipulators. The system is composed of a multiple flexible links and flexible revolute joints manipulator mounted on a mobile platform. First, analyzing on kinematics and dynamics of the model is carried out then; open-loop optimal control approach is presented for optimal motion designing of the system. The problem is known to be complex since combined motion of the base and manipulator, non-holonomic constraint of the base and highly non-linear and complicated dynamic equations as a result of the flexible nature of both links and joints are taken into account. In the proposed method, the generalized coordinates and additional kinematic constraints are selected in such a way that the base motion coordination along the predefined path is guaranteed while the optimal motion trajectory of the end-effector is generated. This method by using Pontryagin’s minimum principle and deriving the optimality conditions converts the optimal control problem into a two point boundary value problem. A comparative assessment of the dynamic model is validated through computer simulations, and then additional simulations are done for trajectory planning of a two-link flexible mobile manipulator to demonstrate effectiveness and capability of the proposed approach.     

Feasible command strategies for the control of motion of a simple mobile robot

The concept of feasible command strategies is introduced and its applicability is demonstrated by solving a guidance and control problem. This problem concerns the motion of a system which is composed of a rolling disk and a controlled slender rod that is pivoted, through its endpoint, about the disk center. The motion of the disk-rod system is subjected to state and control constraints, and it serves as a model for the motion of a simple mobile robot. In addition, the concept of path controllability is introduced and a condition is derived for the system motion path controllability. The derivation of this condition enables one to design closed-loop control laws for the system motion.     

The shortest path problem with forbidden paths

We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints.     

Optimal paths in bi-attribute networks with fractional cost functions

An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times.     

A two-phase ant colony algorithm for multi-echelon defective supply chain network design

Supply chain system is an integrated production system of a product. In the past researches, this system was often assumed to be an equilibrium structure, but in real production process, some members in this system usually cannot effectively complete their production task because of the losses of production, which will reduce the performance of the whole supply chain production system. This supply chain with the losses of production is called the defective supply chain (DSC) system. This research will discuss the partner selection and the production–distribution planning in this DSC network system. Besides the cost of production and transportation, the reliability of the structure and the unbalance of this system caused by the losses of production are considered. Then a germane mathematical programming model is developed for solving this problem. Due to the complex problem and in order to get a satisfactory near-optimal solution with great speed, this research proposes seeking the solution with the solving model based on ant colony algorithm. The application results in real cases show that the solving model presented by this research can quickly and effectively plan the most suitable type of the DSC network and decision-making of the production–distribution. Finally, a comparative numerical experiment is performed by using the proposed approach and the common single-phase ant colony algorithm (SAC) to demonstrate the performance of the proposed approach. The analysis results show that the proposed approach can outperform the SAC in partner selection and production–distribution planning for DSC network design.     

Motion Planning in Environments with Low Obstacle Density

We present a simple and efficient paradigm for computing the exact solution of the motion planning problem in environments with a low obstacle density. Such environments frequently occur in practical instances of the motion planning problem. The complexity of the free space for such environments is known to be linear in the number of obstacles. Our paradigm is a new cell decomposition approach to motion planning and exploits properties that follow from the low density of the obstacles in the robot's workspace. These properties allow us to decompose the workspace, subject to some constraints, rather than to decompose the higher-dimensional free configuration space directly. A sequence of uniform steps transforms the workspace decomposition into a free space decomposition of asymptotically the same size. The approach leads to nearly optimal O(n \log n) motion planning algorithms for free-flying robots with any fixed number of degrees of freedom in workspaces with low obstacle density. Received October 17, 1995, and in revised form July 8, 1997, and February 23, 1998.     

Generating optimal path by level set approach for a mobile robot moving in static/dynamic environments

According to the analogy between the mobile robot navigation path and the heat transferring path under steady state, the robot path planning problem during navigation is converted into identify the heat transferring path that minimizes the thermal compliance across the analysis domain. A new path planning approach which combines the concept of growth simulation and level set based heat conduction topology optimization framework is adopted to determine the heat transferring path. By introducing the concept of growth simulation, the proposed approach could calculate a few steps of the navigation path, which is of great significance for online reactive navigation. The proposed approach could avoid local minima and search for the optimal growth orientation freely without constraints from background mesh since the inherent characteristics of heat conduction and the level set approach, respectively. A new reactive navigation algorithm based on the proposed path planning approach and the concept of temporarily safe path is proposed to navigate the mobile robot from the start point to the goal point in unknown dynamic environment with static and dynamic obstacles. Diverse simulation cases are carried to illustrate the effectiveness of the reactive navigation algorithm.     

A genetic-fuzzy approach for mobile robot navigation among moving obstacles

In this paper, a genetic-fuzzy approach is developed for solving the motion planning problem of a mobile robot in the presence of moving obstacles. The application of combined soft computing techniques — neural network, fuzzy logic, genetic algorithms, tabu search and others — is becoming increasingly popular among various researchers due to their ability to handle imprecision and uncertainties that are often present in many real-world problems. In this study, genetic algorithms are used for tuning the scaling factors of the state variables (keeping the relative spacing of the membership distributions constant) and rule sets of a fuzzy logic controller (FLC) which a robot uses to navigate among moving obstacles. The use of an FLC makes the approach easier to be used in practice. Although there exist many studies involving classical methods and using FLCs they are either computationally extensive or they do not attempt to find optimal controllers. The proposed genetic-fuzzy approach optimizes the travel time of a robot off-line by simultaneously finding an optimal fuzzy rule base and optimal scaling factors of the state variables. A mobile robot cant then use this optimal FLC on-line to navigate in presence of moving obstacles. The results of this study on a number of problem scenarios show that the proposed genetic-fuzzy approach can produce efficient knowledge base of an FLC for controlling the motion of a robot among moving obstacles.     

Path planning for robots under stochastic uncertainty *

In order to reduce large online measurement and correction expenses, the a priori informations on the random variations of the model parameters of a robot and its working environment are taken into account already at the planning stage. Thus, instead of solving a deterministic path planning problem with a fixed nominal parameter vector, here, the optimal velocity profile along a given trajectory in work space is determined by using a stochastic optimization approach. Especially, the standard polygon of constrained motion-depending on the nominal parameter vector-is replaced by a more general set of admissible motion determined by chance constraints or more general risk constraints. Robust values (with respect to stochastic parameter variations) of the maximum, minimum velocity, acceleration, deceleration, resp., can be obtained then by solving a univariate stochastic optimization problem Considering the fields of extremal trajectories, the minimum-time path planning problem under stochastic uncertainty can be solved now by standard optimal deterministic path planning methods     

Dynamic Location-routeing Problems

Dynamic location-routeing problems involve the determination of the least-cost sequence of depot, vehicle fleet and route configurations in a distribution system, over a given planning horizon. This paper presents two solution approaches to such problems. The first is an exact method which is appropriate for small-scale problems. It consists of representing the problem by a suitable network and of solving to optimality an integer linear programme associated with the network. In the second approach, some of the system costs are approximated, and a global solution is then obtained by determining a shortest path on a directed graph. Under some hypotheses, this approach is suitable for large-scale problems. It is illustrated on a simple example.     

Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context

This paper presents a unified three-stage approach (TSA), comprising preprocessing, setup, and iterative solution stages, for solving several variations of the resource constrained shortest-path problem (RCSP). TSA is designed specially for column-generation applications in which sub-problems must be solved repetitively. The first two stages are implemented one time and only the third stage need be applied repetitively. In a companion paper, the authors proposed a TSA for solving RCSP on an acyclic graph with upper bound resource-limitation constraints. This paper shows that a TSA can be designed to solve each of several related problems: shortest-path with equality resource-limitation constraints; shortest-path with resource windows; resource-constrained, k-shortest path; and multiple-resource, multiple-choice knapsack. A numerical example demonstrates application of a TSA to design an international assembly system and its supply chain using branch and price with multiple-choice knapsack sub-problems. Computational results show that our TSA can solve this sub-problem effectively in such a column-generation environment.     

Design of LMI‐based sliding mode controller with an exponential policy for a class of underactuated systems

In this article, a novel sliding mode control (SMC) approach is proposed for the control of a class of underactuated systems which are featured as in cascaded form with external disturbances. The asymptotic stability conditions on the error dynamical system are expressed in the form of linear matrix inequalities. The control objective is to construct a controller such that would force the state trajectories to approach the sliding surface with an exponential policy. The proposed SMC has a simple structure because it is derived from the associated first‐order differential equation and is capable of handling system disturbances and nonlinearities. The effectiveness of the proposed control method is validated using intensive simulations. © 2014 Wiley Periodicals, Inc. Complexity 21: 117–124, 2016     

Combined time and energy optimal trajectory planning with quadratic drag for mixed discrete-continuous task planning

ABSTRACT

The problem of mixed discrete-continuous task planning for mechanical systems, such as aerial drones or other autonomous units, can be often treated as a sequence of point-to-point trajectories. In this work, the problem of optimal trajectory planning under a combined completion time and energy criterion, for a straight point to point path for a second-order system with quadratic under state (velocity) and control (acceleration) constraints is considered. The solution is obtained and proved to be optimal using the Pontryagin Maximum Principle. Simulation results for different cases are presented and compared with a customary numerical optimal control solver.     

Exact methods for large-scale multi-period financial planning problems

A relevant financial planning problem is the periodical rebalance of a portfolio of assets such that the portfolio’s total value exhibits certain characteristics. This problem can be modelled using a transition graph G to represent the future state space evolution of the corresponding economy and mathematically formulated as a linear programming problem. We present two different mathematical formulations of the problem. The first considers explicitly the set of the possible scenarios (scenario-based approach), while the second considers implicitly the whole set of scenarios provided by the graph G (graph-based approach). Unfortunately, for both the formulations the size of the corresponding linear programs can be huge even for simple financial problems. However, the graph-based approach seems to be a more powerful model, since it allows to consider a huge number of scenarios in a very compact formulation. The purpose of this paper is to present both heuristic and exact methods for the solution of large-scale multi-period financial planning problems using the graph-based model. In particular, in this paper we propose lower and upper bounds and three exact methods based on column, row and column/row generation, respectively. Since the methods based on column/row generation exploits simultaneously both the primal and the dual structure of the problem we call it Criss-Cross generation method. Computational results are given to prove the effectiveness of the proposed methods.      

A simple approach to fuzzy critical path analysis in project networks

This paper develops a simple approach to critical path analysis in a project network with activity times being fuzzy numbers. The idea is based on the linear programming (LP) formulation and fuzzy number ranking method. The fuzzy critical path problem is formulated as an LP model with fuzzy coefficients of the objective function, and then on the basis of properties of linearity and additivity, the Yager’s ranking method is adopted to transform the fuzzy LP formulation to the crisp one which can be solved by using the conventional streamlined solution methods. Consequently, the critical path and total duration time can be obtained from the derived optimal solution. Moreover, in this paper we also define the most critical path and the relative path degree of criticality, which are theoretically sound and easy to use in practice. An example discussed in some previous studies illustrates that the proposed approach is able to find the most critical path, which is proved to be the same as that derived from an exhausted comparison of all possible paths. The proposed approach is very simple to apply, and it is not require knowing the explicit form of the membership functions of the fuzzy activity times.     

ON/OFF strategy based minimum-time control of continuous Petri nets

This paper focuses on the target marking control problem of timed continuous Petri nets (TCPN), aiming to drive the system from an initial state to a desired final one. This problem is similar to the set-point control problem in a general continuous-state system. In a previous work, a simple and efficient ON/OFF controller was proposed for Choice-Free nets, and it was proved to be minimum-time (Wang, 2010). However, for general TCPN the ON/OFF controller may bring the system to “blocking” situations due to its “greedy” firing strategy, and the convergence to the final state is not ensured. In this work the ON/OFF controller is extended to general TCPN by adding more “fair” strategies to solve conflicts in the system: the ON/OFF+ controller is obtained by forcing proportional firings of conflicting transitions. Nevertheless, such kind of controller might highly slow down the system when transitions have flows of different orders of magnitude, therefore a balancing process is introduced, leading to the B-ON/OFF controller. A third approach introduced here is the MPC-ON/OFF controller, a combination of Model Predictive Control (MPC) and the ON/OFF strategy; it may achieve a smaller number of time steps for reaching the final states, but usually requires more CPU time for computing the control laws. All the proposed extensions are heuristic methods for the minimum-time control and their convergences are proved. Finally, an application example of a manufacturing cell is considered to illustrate the methods. It is shown that by using the proposed controllers, reasonable numbers of time steps for reaching the final state can be obtained with low computational complexity.     

Evaluation model of problem solving

Problem solving is a style of thinking, which transforms a given problem to the goal state through a so-called PS (problem solving) path. Different from the traditional GPS (General Problem Solver) approach, the focus in this paper is placed on how to judge the performance of PS paths, that is, the evaluation problem of problem solving.A series of PS paths point from the given source problem to the destination goal, then form a PSN (PS Network). This paper proposes an elaborated CPSN (Coordinate Problem Solving Network) as the evaluation model of problem solving. In CPSN, each problem is assigned a unique coordinate and then each PS path can have an evaluation vector. Several examples show such arrangement can give more insight to PS paths.Furthermore, an incremental learning algorithm is developed for the update of CPSN. When a new PS path is obtained, it is not necessary to recalculate the whole CPSN. Examples show such algorithm provides a more efficient way in finding new PS paths.     

Minimum cost multi-product flow lines

In this paper, the problem of finding the minimum cost flow line able to produce different products is considered. This problem can be formulated as a shortest path problem on an acyclic di-graph when the machines graph associated with each product family is a chain or a comb. These graphs are relevant in production planning when dealing with pipelined assembly systems. We solve the problem using A ^* algorithm which can be efficiently exploited when there is a good estimate on the value of an optimal solution. Therefore, we adapt a known bound for the Shortest Common Supersequence problem to our case and show the effectiveness of the approach by presenting an extensive computational experience.