Dynamic motion planning in low obstacle density environments

A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and realistic low obstacle density (L.O.D.) assumption results in linear complexity in the number of obstacles of the free space (Van der Stappen et al., 1997). In this paper we address the dynamic version of the motion planning problem in which a robot moves among polygonal obstacles which move along polylines. The obstacles are assumed to move along constant complexity polylines, and to respect the low density property at any given time. We will show that in this situation a cell decomposition of the free space of size O(n²(n) log² n) can be computed in O(n²(n) log² n) time. The dynamic motion planning problem is then solved in O(n²(n) log³ n) time. We also show that these results are close to optimal.     

Feasibility of motion planning on acyclic and strongly connected directed graphs

Motion planning is a fundamental problem of robotics with applications in many areas of computer science and beyond. Its restriction to graphs has been investigated in the literature, for it allows one to concentrate on the combinatorial problem abstracting from geometric considerations. In this paper, we consider motion planning over directed graphs, which are of interest for asymmetric communication networks. Directed graphs generalize undirected graphs, while introducing a new source of complexity to the motion planning problem: moves are not reversible. We first consider the class of acyclic directed graphs and show that the feasibility can be solved in time linear in the product of the number of vertices and the number of arcs. We then turn to strongly connected directed graphs. We first prove a structural theorem for decomposing strongly connected directed graphs into strongly biconnected components. Based on the structural decomposition, we show that the feasibility of motion planning on strongly connected directed graphs can be decided in linear time.     

Heuristic optimization methods for motion planning of autonomous agricultural vehicles

In this paper, two heuristic optimization techniques are tested and compared in the application of motion planning for autonomous agricultural vehicles: Simulated Annealing and Genetic Algorithms. Several preliminary experimentations are performed for both algorithms, so that the best neighborhood definitions and algorithm parameters are found. Then, the two tuned algorithms are run extensively, but for no more than 2000 cost function evaluations, as run-time is the critical factor for this application. The comparison of the two algorithms showed that the Simulated Annealing algorithm achieves the better performance and outperforms the Genetic Algorithm. The final optimum found by the Simulated Annealing algorithm is considered to be satisfactory for the specific motion planning application.     

Entropy estimations for motion planning problems in robotics

This is the concluding work of our series devoted to the evaluation of the complexity and entropy of a motion planning problem for a sub-Riemannian distribution. We consider some new cases of the dimension and codimension of the distribution, in particular, (2, 3), (3, 4), and some other that are one-step-bracket-generating. We summarize all known estimations for low-dimensional generic systems. They include all generic systems of corank less than 4 and other cases up to corank 10. Published in Russian in Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2007, Vol. 256, pp. 70–88.     

Path planning in formation and collision avoidance for multi-agent systems

This paper investigates, in a centralized manner, the motion planning problem for a team of unicycle-like mobile robots in a known environment. In particular, a multi-agent collision-free patrolling and formation control algorithm is presented, which combines outcomes of: (i) stability analysis of hybrid systems, (ii) algebraic geometry, and (iii) classical potential functions. The objective is achieved by designing a Lyapunov-based hybrid strategy that autonomously selects the navigation parameters. Tools borrowed from algebraic geometry are adopted to construct Lyapunov functions that guarantee the convergence to the desired formation and path, while classical potential functions are exploited to avoid collisions among agents and the fixed obstacles within the environment. The proposed navigation algorithm is tested in simulation and then validated by using the robots of a remote accessible robotic testbed.     

Structural analysis of optimization problems formulated in planning languages

Computer-assisted model analysis, verification, and debugging is growing in importance. Most mathematical programming systems provide some debugging tools. This paper describes a typical structural analysis problem encountered in optimization models formulated in planning languages and states results that are useful in resolving it.This research was partially supported by ONR Contract No. N00014-78-C-0222.     

A historical note on the complexity of scheduling problems

In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented linear-time reductions of the partition problem to a number of scheduling problems. Unaware of complexity theory, they argued that, since partition is not known to have a simple algorithm, one cannot expect to find simple algorithms for these scheduling problems either. Their work did not go completely unnoticed, but it received little recognition. We describe the approach and review the results.     

A stochastic programming approach for planning horizons of infinite horizon capacity planning problems

Planning horizon is a key issue in production planning. Different from previous approaches based on Markov Decision Processes, we study the planning horizon of capacity planning problems within the framework of stochastic programming. We first consider an infinite horizon stochastic capacity planning model involving a single resource, linear cost structure, and discrete distributions for general stochastic cost and demand data (non-Markovian and non-stationary). We give sufficient conditions for the existence of an optimal solution. Furthermore, we study the monotonicity property of the finite horizon approximation of the original problem. We show that, the optimal objective value and solution of the finite horizon approximation problem will converge to the optimal objective value and solution of the infinite horizon problem, when the time horizon goes to infinity. These convergence results, together with the integrality of decision variables, imply the existence of a planning horizon. We also develop a useful formula to calculate an upper bound on the planning horizon. Then by decomposition, we show the existence of a planning horizon for a class of very general stochastic capacity planning problems, which have complicated decision structure.     

Combining linear programming and automated planning to solve intermodal transportation problems

When dealing with transportation problems Operational Research (OR), and related areas as Artificial Intelligence (AI), have focused mostly on uni-modal transport problems. Due to the current existence of bigger international logistics companies, transportation problems are becoming increasingly more complex. One of the complexities arises from the use of intermodal transportation. Intermodal transportation reflects the combination of at least two modes of transport in a single transport chain, without a change of container for the goods. In this paper, a new hybrid approach is described which addresses complex intermodal transport problems. It combines OR techniques with AI search methods in order to obtain good quality solutions, by exploiting the benefits of both kinds of techniques. The solution has been applied to a real world problem from one of the largest spanish companies using intermodal transportation, Acciona Transmediterránea Cargo.     

On solving stochastic production planning problems via scenario modelling

Summary Linear Porgramming models for stochastic planning problems and a methodology for solving them are proposed. A production planning problem with uncertainty in demand is used as a test case, but the methodology presented here is applicable to other types of problems as well. In these models, uncertainty in demand is characterized via scenarios. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield an implementable non-anticipative policy. Such an approach makes it possible to model correlated and nonstationary demand as well as a variety of recourse decision types. For computational purposes, two alternative representations are proposed. A compact approach that is suitable for the Simplex method and a splitting variable approach that is suitable for the Interior Point Methods. A crash procedure that generates an advanced starting solution for the Simplex method is developed. Computational results are reported with both the representations. Although some of the models presented here are very large (over 25000 constraints and 75000 variables), our computational experience with these problems is quite encouraging.     

Computational complexity of some scheduling problems with multiprocessor tasks

The paper is concerned with scheduling problems with multiprocessor tasks and presents conditions under which such problems can be solved in polynomial time. The application of these conditions is illustrated by two quite general scheduling problems. These results are complemented by a proof of NP-hardness of the problem with a UET task system, two parallel processors, the criterion of total completion time, and precedence constraints in the form of out-trees.     

A heuristic approach for big bucket multi-level production planning problems

Multi-level production planning problems in which multiple items compete for the same resources frequently occur in practice, yet remain daunting in their difficulty to solve. In this paper, we propose a heuristic framework that can generate high quality feasible solutions quickly for various kinds of lot-sizing problems. In addition, unlike many other heuristics, it generates high quality lower bounds using strong formulations, and its simple scheme allows it to be easily implemented in the Xpress-Mosel modeling language. Extensive computational results from widely used test sets that include a variety of problems demonstrate the efficiency of the heuristic, particularly for challenging problems.     

Maximum thick paths in static and dynamic environments

We consider the problem of finding a large number of disjoint paths for unit disks moving amidst static or dynamic obstacles. The problem is motivated by the capacity estimation problem in air traffic management, in which one must determine how many aircraft can safely move through a domain while avoiding each other and avoiding “no-fly zones” and predicted weather hazards. For the static case we give efficient exact algorithms, based on adapting the “continuous uppermost path” paradigm. As a by-product, we establish a continuous analogue of Menger's Theorem.Next we study the dynamic problem in which the obstacles may move, appear and disappear, and otherwise change with time in a known manner; in addition, the disks are required to enter/exit the domain during prescribed time intervals. Deciding the existence of just one path, even for a 0-radius disk, moving with bounded speed is NP-hard, as shown by Canny and Reif [J. Canny, J.H. Reif, New lower bound techniques for robot motion planning problems, in: Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49–60]. Moreover, we observe that determining the existence of a given number of paths is hard even if the obstacles are static, and only the entry/exit time intervals are specified for the disks. This motivates studying “dual” approximations, compromising on the radius of the disks and on the maximum speed of motion.Our main result is a pseudopolynomial-time dual-approximation algorithm. If K unit disks, each moving with speed at most 1, can be routed through an environment, our algorithm finds (at least) K paths for disks of radius somewhat smaller than 1 moving with speed somewhat larger than 1.     

Solving certain singly constrained convex optimization problems in production planning

This paper considers the problem of minimizing a special convex function subject to one linear constraint. Based upon a theorem for lower and upper bounds on the Lagrange multiplier a fully polynomial time approximation scheme is proposed. The efficiency of the algorithm is demonstrated by a computational experiment.     

Criterion function for accessibility,uncertainty problems in regional land-use planning

One objective in regional planning is the creation of communities with great accessibility. Thus we should plan the locations of inhabitants and the activities of the region so that the total accessibility will be maximized subject to some restrictions. This is a quadratic programming problem, which can be solved by quadratic programming techniques, but we cannot then take into account the uncertainties of the problem.In this paper a new criterion function is proposed for accessibility, uncertainty problems in regional land-use planning. It is derived from Hurwicz's generalized maximin principle. Many advantages are gained, for the planning problem is separated into linear programming problems, the uncertainties are taken into consideration as in game theory and the methods of parametric programming are available.A simplified problem of the populations of three town areas is studied and the method is generalized for problems of many activities and areas.     

Design,planning, scheduling,and control problems of flexible manufacturing systems

The design and use of flexible manufacturing systems (FMSs) involve some intricate operations research problems.FMS design problems include, for example, determining the appropriate number of machine tools of each type, the capacity of the material handling system, and the size of buffers.FMS planning problems include the determination of which parts should be simultaneously machined, the optimal partition of machine tools into groups, allocations of pallets and fixtures to part types, and the assignment of operations and associated cutting tools among the limited-capacity tool magazines of the machine tools.FMS scheduling problems include determining the optimal input sequence of parts and an optimal sequence at each machine tool given the current part mix.FMS control problems are those concerned with, for example, monitoring the system to be sure that requirements and due dates are being met and that unreliability problems are taken care of. This paper defines and describes these FMS problems in detail for OR/MS researchers to work on.     

A methodology to solve large-scale cooperative transportation planning problems

In this paper, we suggest a methodology to solve a cooperative transportation planning problem and to assess its performance. The problem is motivated by a real-world scenario found in the German food industry. Several manufacturers with same customers but complementary food products share their vehicle fleets to deliver their customers. After an appropriate decomposition of the entire problem into sub problems, we obtain a set of rich vehicle routing problems (VRPs) with time windows for the delivery of the orders, capacity constraints, maximum operating times for the vehicles, and outsourcing options. Each of the resulting sub problems is solved by a greedy heuristic that takes the distance of the locations of customers and the time window constraints into account. The greedy heuristic is improved by an appropriate Ant Colony System (ACS). The suggested heuristics to solve the problem are assessed within a dynamic and stochastic environment in a rolling horizon setting using discrete event simulation. We describe the used simulation infrastructure. The results of extensive simulation experiments based on randomly generated problem instances and scenarios are provided and discussed. We show that the cooperative setting outperforms the non-cooperative one.     

Dispatch planning using newsvendor dual problems and occupation times: Application to hydropower

We consider price-driven dispatch planning under price uncertainty: A storable commodity is optimally sold and purchased over time. First, we consider models where the storage level is constrained in expectation. The dual of the corresponding optimization problem is related to the newsvendor problem. Exact solutions of bang-bang type are given. The second methodology is for high-frequency dispatch decisions in multistage stochastic programming models: To overcome the curse of dimensionality, prices are modeled by occupation times at price levels. In a case study, we consider a pumped-storage hydropower plant: Numerical solutions are given, which have similar patterns as for the first, exactly solvable problems.     

On relocation problems with multiple identical working crews

The relocation problem was formulated from a public housing project. In its basic form, a set of buildings needed to be torn down and erected by a single working crew. Given a fixed budget, the relocation problem seeks to determine a feasible reconstruction sequence of the old buildings. This problem has been shown to be mathematically equivalent to the classical two-machine flowshop of makespan minimization. In this paper, we consider a variant where multiple working crews are available for the redevelopment project. Most of our results center on the situations where all buildings require the same redevelopment time. We first present a strong NP-hardness proof for the case with two working crews. Then, we give a negative result about the approximability of the studied problem. Approximation algorithms and associated performance-ratio analysis are designed for the cases with unbounded as well as bounded numbers of machines.