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.     

SOKOBAN and other motion planning problems

We consider a natural family of motion planning problems with movable obstacles and obtain hardness results for them. Some members of the family are shown to be PSPACE-complete thus improving and extending (and also simplifying) a previous NP-hardness result of Wilfong. The family considered includes a motion planning problem which forms the basis of a popular computer game called SOKOBAN. The decision problem corresponding to SOKOBAN is shown to be NP-hard. The motion planning problems considered are related to the “warehouseman's problem” considered by Hopcroft, Schwartz and Sharir, and to geometric versions of the motion planning problem on graphs considered by Papadimitriou, Raghavan, Sudan and Tamaki.     

Pushing Squares Around

We study dynamic self-reconfiguration of modular metamorphic systems. We guarantee the feasibility of motion planning in a rectangular model consisting of square modules that are allowed to slide along or rotate about one another. That is, we show that any two connected configurations of the same number of modules can be transformed into each other by a sequence of moves so that all intermediate configurations are connected. This settles a conjecture formulated in [6].     

Optimal Path Planning Based on Visibility

Various problems associated with optimal path planning for mobile observers such as mobile robots equipped with cameras to obtain maximum visual coverage of a surface in the three-dimensional Euclidean space are considered. The existence of solutions to these problems is discussed first. Then, optimality conditions are derived by considering local path perturbations. Numerical algorithms for solving the corresponding approximate problems are proposed. Detailed solutions to the optimal path planning problems for a few examples are given.     

The snowblower problem

We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a snowblower passes over each region along the tour, it displaces snow into a nearby region. The constraint is that if the snow is piled too high, then the snowblower cannot clear the pile.We give an algorithmic study of the SBP. We show that in general, the problem is NP-complete, and we present polynomial-time approximation algorithms for removing snow under various assumptions about the operation of the snowblower. Most commercially available snowblowers allow the user to control the direction in which the snow is thrown. We differentiate between the cases in which the snow can be thrown in any direction, in any direction except backwards, and only to the right. For all cases, we give constant-factor approximation algorithms; the constants increase as the throw direction becomes more restricted. Our results are also applicable to robotic vacuuming (or lawnmowing) with bounded-capacity dust bin.     

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.     

The complexity of the free space for a robot moving amidst fat obstacles

We propose a new definition of fatness of geometric objects and compare it with alternative definitions. We show that, under some realistic assumptions, the complexity of the free space for a robot, with any fixed number of degrees of freedom moving in a d-dimensional Euclidean workspace with fat obstacles, is linear in the number of obstacles. The complexity of motion planning algorithms depends on the complexity of the robot's free space, and theoretically, the complexity of the free space can be very high. Thus, our result opens the way to devising provable efficient motion planning algorithms in certain realistic settings.     

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.     

Quantified propositional calculus and a second-order theory for NC1

Let H be a proof system for quantified propositional calculus (QPC). We define the Σ^q_j-witnessing problem for H to be: given a prenex Σ^q_j-formula A, an H-proof of A, and a truth assignment to the free variables in A, find a witness for the outermost existential quantifiers in A. We point out that the Σ^q₁-witnessing problems for the systems G^*₁and G₁ are complete for polynomial time and PLS (polynomial local search), respectively. We introduce and study the systems G^*₀ and G₀, in which cuts are restricted to quantifier-free formulas, and prove that the Σ^q_j-witnessing problem for each is complete for NC¹. Our proof involves proving a polynomial time version of Gentzen’s midsequent theorem for G^*₀ and proving that G₀-proofs are TC⁰-recognizable. We also introduce QPC systems for TC⁰ and prove witnessing theorems for them. We introduce a finitely axiomatizable second-order system VNC¹ of bounded arithmetic which we prove isomorphic to Arai’s first order theory AID + Σ^b ₀-CA for uniform NC¹. We describe simple translations of VNC¹ proofs of all bounded theorems to polynomial size families of G^*₀ proofs. From this and the above theorem we get alternative proofs of the NC¹ witnessing theorems for VNC¹ and AID.This research was carried while this author was a student at the University of Toronto.     

Semi-on-line scheduling problems for maximizing the minimum machine completion time

1. IntroductionThis paper considers the following scheduling problem: We are given a set J = {pl,Pz,', p.} of independent jobs, each with a positive processing time pi, that must be scheduled on m > 1 parallel and identical machines M = {MI, M2,', Mm}. We identify thejobs with their processing times. The jobs and machines are available at time zero, andno preemption is allowed. The objective is to maximize the minimum workload over themaChines. This problem, denoted by PtICmi., is on…     

Variants of Visibility and their Complexity

First we give an overview about variants of visibility and related problems. Then we prove that some guarding and covering problems are NP-hard for ortho-polygons with holes, using a so-called vertex cover technique.     

Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups

A pseudo-natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo-natural algorithm is arbitrarily more complicated than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo-natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented group G from a Turing machine T such that the intrinsic complexity of the word problem for G reflects the complexity of the halting problem of T, while the derivational complexity of the word problem for G reflects the runtime complexity of T. The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40, 20F10.     

Minimizing the number of machines for minimum length schedules

In this paper, we present a new objective function for scheduling on parallel machines: minimizing the number of machines for schedules of minimum length. We study its complexity and we prove the NP-completeness of this problem, even if there is no precedences or for unitary execution times. We propose several polynomial algorithms for various particular cases.     

Nonlinear optimization exclusion tests for finding all solutions of nonlinear equations

Exclusion tests are a well known tool in the area of interval analysis for finding the zeros of a function over a compact domain. Recently, K. Georg developed linear programming exclusion tests based on Taylor expansions. In this paper, we modify his approach by choosing another objective function and using nonlinear constraints to make the new algorithm converges faster than the algorithm in [K. Georg, A new exclusion test, J. Comput. Appl. Math. 152 (2003) 147–160]. In this way, we reduce the number of subinterval in each level. The computational complexity for the new tests are investigated. Also, numerical results and comparisons will be presented.     

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.     

One-dimensional free boundary problem for actin-based propulsion of Listeria

Some bacteria move inside cells by recruiting the actin filaments of the host cells. The filaments are polymerized at the back surface of the bacteria, and they move away, forming a “comet” tail behind the bacterium, which consists of gel network. We develop a one-dimensional mathematical model of the gel based on partial differential equations which involve the number of filaments, the density and velocity of the gel, and the pressure. The two end-points of the gel form two free boundaries. The resulting free boundary problem is rather non-standard. We prove local existence and uniqueness.     

General scheduling non-approximability results in presence of hierarchical communications

We investigate on the issue of minimizing the makespan (resp. the sum of the completion times) for the multiprocessor scheduling problem in presence of hierarchical communications. We consider a model with two levels of communication: interprocessor and intercluster. The processors are grouped in fully connected clusters. We propose general non-approximability results in the case where all the tasks of the precedence graph have unit execution times, and where the multiprocessor is composed of an unrestricted number of machines with l ? 4 identical processors each.