Minimal orientations of colour critical graphs

In 1966 T. Gallai asked whether every criticalk-chromatic graph possesses an orientation having just one directed path of lengthk–1. In this note we show that in general the answer is negative, but also that the answer is affirmative whenk5 and the graph has maximal degree at mostk.     

A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment

We consider the problem of planning the motion of an arbitraryk-sided polygonal robotB, free to translate and rotate in a polygonal environmentV bounded byn edges. We present an algorithm that constructs a single component of the free configuration space ofB in timeO((kn) ^2+ɛ), for any ɛ>0. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying motion-planning problem, within the same running time. Work on this paper by Dan Halperin has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. Work on this paper by Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. A preliminary and extended version of the paper has appeared as: D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment,Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 382–391. Part of the work on the paper was carried out while Dan Halperin was at Tel Aviv University.     

Robot motion planning

We survey recent developments in algorithmic motion planning in robotics. © 1996 John Wiley & Sons, Inc.     

On unavoidable digraphs in orientations of graphs

Let G be a graph, and let D be a directed graph. Write G → D to mean that, no matter how the edges of G are given orientations, a copy of D must appear as a subgraph of the resulting oriented graph. It is proved that among all G for which G → D, the minimum chromatic number is equal to the minimum k for which K_k → hom(D), where hom(D) is the set of homomorphs of D. Next, necessary and sufficient conditions are given for a directed graph to have a homomorphism into a given transitive tournament, directed path, or directed cycle. These results are then applied to various cases of the above theorem. In particular, the minimum chromatic number is evaluated whenever D is an oriented forest, and all D are characterized for which the minimum chromatic number is no more than three.     

On the complexity of a single cell in certain arrangements of surfaces related to motion planning

We obtain near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in certain arrangements ofn surfaces in 3-space where the lower bound for this quantity is Ω(n ²) or slightly larger. We prove a theorem that identifies a collection of topological and combinatorial conditions for a set of surface patches in space, which make the complexity of a single cell in an arrangement induced by these surface patches near-quadratic. We apply this result to arrangements related to motion-planning problems of two types of robot systems with three degrees of freedom and also to a special type of arrangements of triangles in space. The complexity of the entire arrangement in each case that we study can be Θ(n ³) in the worst case, and our single-cell bounds are of the formO(n ² α(n)), O(n ² logn), orO(n ² α(n)logn). The only previously known similar bounds are for the considerably simpler arrangements of planes or of spheres in space, where the bounds are Θ(n) and Θ(n ²), respectively. For some of the arrangements that we study we derive near-quadratic-time algorithms to compute a single cell. A preliminary version of this paper has appeared inProc. 7th ACM Symposium on Computational Geometry, North Conway, NH, 1991, pp. 314–323.     

On the skew energy of orientations of hypercubes

Let D be a digraph of order n and λ₁,λ₂,…,λ_n denote all the eigenvalues of the skew-adjacency matrix of D. The skew energy E_S(D) of D is defined as . In this paper, it is proved that for any positive integer k≥3, there exists a k-regular graph of order n having an orientation D with . This work positively answers a problem proposed by Adiga et al. [C. Adiga, R. Balakrishnan, Wasin So, The skew energy of a digraph, Linear Algebra Appl. 432 (2010) 1825-1835]. In addition, a digraph is also constructed such that its skew energy is the same as the energy of its underlying graph.     

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.     

On Eulerian orientations of even-degree hypercubes

It is well known that every Eulerian orientation of an Eulerian $2k$-edge connected (undirected) graph is strongly $k$-edge connected. A long-standing goal in the area is to obtain analogous results for other types of connectivity, such as node connectivity. We show that every Eulerian orientation of the hypercube of degree $2k$ is strongly $k$-node connected.     

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.     

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.     

Brownian motion and algorithm complexity

The Brownian motion is shown to be a useful tool in analysing some sorting and tree manipulation algorithms.     

Computer-aided motion planning for satellite mounted robots

In space-based robotics, one of the most important problems is the disturbance to the satellite attitude and to the satellite microgravity environment caused by satellite mounted robot operation. This paper reports on computer-aided motion planning strategies to overcome this problem. Point-to-point motion designs are generated which not only connect prescribed start and end points of the robot motion, but also simultaneously return the satellite to its original attitude. Theoretical characterizations of some of those motion designs are presented, as well as numerical results. The computation time required to produce such motion designs is 1 or 2 min on a workstation. Thus, it can be practical to use these motion plans in space. © 1998 B. G. Teubner Stuttgart–John Wiley & Sons Ltd.     

An exact algorithm for kinodynamic planning in the plane

Planning time-optimal motions has been a major focus of research in robotics. In this paper we consider the following problem: given an object in two-dimensional physical space, an initial point, and a final point, plan a time-optimal obstacle-avoiding motion for this object subject to bounds on the velocity and acceleration of the object. We give the first algorithm which solves the problem exactly in the case where the velocity and acceleration bounds are given in theL _∞ norm. We further prove the following important results: a tracking lemma and a loop-elimination theorem, both of which are applicable to the case of arbitrary norms. The latter result implies that, with or without obstacles, a path which intersects itself can be replaced by one which does not do so and which takes time less than or equal to that taken by the original path. The work of J. Canny and A. Rege was supported by NSF Grants IRI-89-58577 and IRI-90-14490 and by a David and Lucile Packard Fellowship. J. Reif's work was supported in part by DARPA/ARO Contract DAAL03-88-K-0185, Air Force Contract AFSOR-87-0386, ONR Contract N00014-K-0310, and DARPA/ISTO Contract N00014-88-K-0458.     

On the dynamic model and motion planning for a spherical rolling robot actuated by orthogonal internal rotors

The paper deals with the dynamics of a spherical rolling robot actuated by internal rotors that are placed on orthogonal axes. The driving principle for such a robot exploits nonholonomic constraints to propel the rolling carrier. A full mathematical model as well as its reduced version are derived, and the inverse dynamics are addressed. It is shown that if the rotors are mounted on three orthogonal axes, any feasible kinematic trajectory of the rolling robot is dynamically realizable. For the case of only two rotors the conditions of controllability and dynamic realizability are established. It is shown that in moving the robot by tracing straight lines and circles in the contact plane the dynamically realizable trajectories are not represented by the circles on the sphere, which is a feature of the kinematic model of pure rolling. The implication of this fact to motion planning is explored under a case study. It is shown there that in maneuvering the robot by tracing circles on the sphere the dynamically realizable trajectories are essentially different from those resulted from kinematic models. The dynamic motion planning problem is then formulated in the optimal control settings, and properties of the optimal trajectories are illustrated under simulation.     

On the tour planning problem

Increasingly, tourists are planning trips by themselves using the vast amount of information available on the Web. However, they still expect and want trip plan advisory services. In this paper, we study the tour planning problem in which our goal is to design a tour trip with the most desirable sites, subject to various budget and time constraints. We first establish a framework for this problem, and then formulate it as a mixed integer linear programming problem. However, except when the size of the problem is small, say, with less than 20–30 sites, it is computationally infeasible to solve the mixed-integer linear programming problem. Therefore, we propose a heuristic method based on local search ideas. The method is efficient and provides good approximation solutions. Numerical results are provided to validate the method. We also apply our method to the team orienteering problem, a special case of the tour planning problem which has been considered in the literature, and compare our method with other existing methods. Our numerical results show that our method produces very good approximation solutions with relatively small computational efforts comparing with other existing methods.     

On the critical graph conjecture

Gol'dberg has recently constructed an infinite family of 3-critical graphs of even order. We now prove that if there exists a p(≥4)-critical graph K of odd order such that K has a vertex u of valency 2 and another vertex v ≠ u of valency ≤(p + 2)/2, then there exists a p-critical graph of even order.