Multiple distributed controllers have been used in software-defined networks (SDNs) to improve scalability and reliability, where each controller manages one static partition of the network. In this paper, we show that dynamic mapping between switches and controllers can improve efficiency in managing traffic load variations. In particular, we propose balanced controller (BalCon) and BalConPlus, two SDN switch migration schemes to achieve load balance among SDN controllers with small migration cost. BalCon is suitable for the scenarios where the network does not require a serial processing of switch requests. For other scenarios, BalConPlus is more suitable, as it is immune to the switch migration blackout and does not cause any service disruption. Simulations demonstrate that BalCon and BalConPlus significantly reduce the load imbalance among SDN controllers by migrating only a small number of switches with low computation overhead. We also build a prototype testbed based on the open-source SDN framework RYU to verify the practicality and effectiveness of BalCon and BalConPlus. Experiment confirms the results of the simulations. It also shows that BalConPlus is immune to switch migration blackout, an adverse effect in the baseline BalCon.

Scalability and reliability are among the main concerns in large-scale Software Defined Networking (SDN) application scenarios. A common approach is to use multiple distributed controllers, each managing one static partition of the network. In this paper, we show that dynamic mapping can improve efficiency in managing traffic load variations. We then propose BalCon (Balanced Controller): an algorithmic solution designed to tackle and reduce the load imbalance among SDN controllers through proper SDN switch migrations. Simulations demonstrate that BalCon is lightweight from the computational point of view and reduces the load imbalance among SDN controllers (expressed as variance) by 40% by migrating only a small number of switches. We also built a realistic prototype of SDN controller, BalConController, based on the open-source SDN framework RYU.

Packet networks need to maintain the state in the form of forwarding tables at each switch. The cost of this state increases as networks support ever more sophisticated per-flow routing, traffic engineering, and service chaining. Per-flow or per-path state at the switches can be eliminated by encoding each packet's desired path in its header. A key component of such a method is an efficient encoding of paths through the network. We introduce a mathematical formulation of this optimal path-encoding problem. We prove that the problem is APX-hard, by showing that approximating it to within a factor less than 8/7 is NP-hard. Thus, at best, we can hope for a constant-factor approximation algorithm. We then present such an algorithm, approximating the optimal path-encoding problem to within a factor 2. Finally, we provide the empirical results illustrating the effectiveness of the proposed algorithm.

The advent of virtualization, containerization and the Internet of Things (IoT) is leading to an explosive growth in the number of endpoints. Ideally with Software Defined Networking (SDN), one would like to customize packet handling for each of these endpoints or applications. However this typically leads to a large growth in forwarding state. This growth is avoided in current networks by using aggregation which trades off fine-grained control of micro-flows for reduced forwarding state. It is worthwhile to ask whether the benefits of micro-flow control can be retained without a large growth in forwarding state and without using aggregation. In this paper we describe an incrementally deployable SDN-friendly packet forwarding mechanism called Path Switching that achieves this by compactly encoding a packet's path through the network in the packet's existing address fields. Path Switching provides the same reduction in forwarding state as source routing while retaining the benefits and use of fixed size packet headers and existing protocols.

A single-sink confluent flow is a routing of multiple demands to a sink r such that any flow exiting a node v must use a single arc. Hence, a confluent flow routes on a tree within the network. In uncapacitated (or uniform-capacity) networks, there is an O(1)-approximation algorithm for demand maximization and a logarithmic approximation algorithm for congestion minimization [6]. We study the case of capacitated networks, where each node v has its own capacity μ(v). Indeed, it was recently shown that demand maximization is in approximable to within polynomial factors in capacitated networks [20]. We circumvent this lower bound in two ways. First, we prove that there is a polylogarithmic approximation algorithm for demand maximization in networks that satisfy the ubiquitous no-bottleneck assumption (NBA). Second, we show a bicriteria result for capacitated networks without the NBA: there is a polylog factor approximation guarantee for demand maximization provided we allow congestion 2. We model the capacitated confluent flows problem using a multilayer linear programming formulation. At the heart of our approach for demand maximization is a rounding procedure for flows on multilayer networks which can be viewed as a proposal algorithm for an extension of stable matchings. In addition, the demand maximization algorithms require, as a subroutine, an algorithm for approximate congestion minimization in a special class of capacitated networks that may be of independent interest. Specifically, we present a polylogarithmic approximation algorithm for congestion minimization in monotonic networks - those networks with the property that μ(u) ≤ μ(v) for each arc (u, v).

Topology managers expose network information to applications to improve application-level resource management. An example for various ongoing standardization activities is Application-Layer Traffic Optimization (ALTO). Due to privacy and security constraints, exposed network information has to be filtered according to policies. As part of such policies, distance information can be abstracted by presenting coarser distances over pairs of clustered nodes rather than the precise distances between all node pairs. We refer to this process as distance sparsification. The contribution of this paper is two-fold, the first being a new policy system to enforce abstraction. The second and the main contribution addresses the algorithmic challenge. For the latter, we consider two types of distance sparsification algorithms. The first variant takes as input a matrix of pairwise distances. The sparsification algorithm produces a smaller distance matrix by clustering the nodes into clusters. The second variant instead collapses an edge-weighted graph. We measure the performance of the algorithms by the accuracy of the resulting sparsified distances, and we show that matrix sparsification outperforms graph sparsification. We further observe the trade-off between the accuracy and the size of the sparsified representation. In addition, we also extend our algorithms to handle labeled data, i. e., abstraction policies explicitly mark a number of destinations as reference points. Such additional information can improve the distance sparsification.

Packet networks need to maintain state in the form of forwarding tables at each switch. The cost of this state increases as networks support ever more sophisticated per-flow routing, traffic engineering, and service chaining. Per-flow or per-path state at the switches can be eliminated by encoding each packet's desired path in its header. A key component of such a method is an efficient encoding of paths through the network. We introduce a mathematical formulation of this optimal path-encoding problem. We prove that the problem is APX-hard, by showing that approximating it to within a factor less than 8/7 is NP-hard. Thus, at best we can hope for a constant-factor approximation algorithm. We then present such an algorithm, approximating the optimal path-encoding problem to within a factor 2. Finally, we provide empirical results illustrating the effectiveness of the proposed algorithm.

The emergence of new capabilities such as virtualization and elastic (private or public) cloud computing infrastructures has made it possible to deploy multiple applications, on demand, on the same cloud infrastructure. A major challenge to achieve this possibility, however, is that modern applications are typically distributed, structured systems that include not only computational and storage entities, but also policy entities (e.g., load balancers, firewalls, intrusion prevention boxes). Deploying applications on a cloud infrastructure without the policy entities may introduce substantial policy violations and/or security holes. In this paper, we present PACE: the first systematic framework for Policy-Aware Application Cloud Embedding. We precisely define the policy-aware, cloud application embedding problem, study its complexity and introduce simple, efficient, online primal-dual algorithms to embed applications in cloud data centers. We conduct evaluations using data from a real, large campus network and a realistic data center topology to evaluate the feasibility and performance of PACE. We show that deployment in a cloud without considering in-network policies may lead to a large number of policy violations (e.g., using tree routing as a way to enforce in-network policies may observe up to 91% policy violations). We also show that our embedding algorithms are very efficient by comparing with a good online fractional embedding algorithm.

Access networks, in particular, Digital Subscriber Line (DSL) equipment, are a significant source of energy consumption for wireline operators. Replacing large monolithic DSLAMs with smaller remote DSLAM units closer to customers can reduce the energy consumption as well as increase the reach of the access network. This paper attempts to formalize the design and optimization of the “last mile” wireline access network with energy as one of the costs to be minimized. In particular, the placement of remote DSLAM units needs to be optimized. We propose solutions for two scenarios. For the scenario where an existing all-copper network from the central office to the customers is to be transformed into a fiber-copper network with remote DSLAM units, we present efficient polynomial-time solutions. For the green-field scenario, where both the access network layout and the placement of remote DSLAM units must be determined, we show that this problem is NP-complete. We present an optimal ILP formulation and also design an efficient heuristic-based approach to build a power and cost optimized access network. Our heuristic-based approach yields results that are very close to optimal. We show how the power consumption of the access network can be reduced by carefully planning the access network and introducing remote DSLAM units.

We show that existing methods for primary-backup replication may disrupt the timing behavior of an underlying service to the extent of making it unusable. We prove that the problem is inherent to the primary-backup model.

The Border Gateway Protocol (BGP) is the interdomain routing protocol used to exchange routing information between Autonomous Systems (ASes) in the internet today. While intradomain routing protocols such as RIP are basically distributed algorithms for solving shortest path problems, the graph theoretic problem that BGP is trying to solve is the stable paths problem (SPP). Unfortunately, unlike shortest path problems, it has been shown that instances of SPP can fail to have a solution, and so BGP can fail to converge. We define a fractional version of SPP and show that all instances of fractional SPP have solutions. We also show that there are polynomial time reductions from a number of well-known graph problems to SPP. For example, finding stable matchings in hypergraphic preference systems (a generalization of graph stable matchings to the case of hypergraphs) and computing kernels in directed graphs are both polynomial time reducible to SPP. These reductions remain valid in the fractional case. Thus the existence of a polynomial time algorithm for computing fractional solutions to SPP would imply polynomial time algorithms for fractional solutions to these other problems as well.

A d-furcated flow is a network flow whose support graph has maximum out degree d. Take a single-sink multi-commodity flow problem on any network and with any set of routing demands. Then we show that the existence of feasible fractional flow with node congestion one implies the existence of a d-furcated flow with congestion at most 1+1/(d-1), for d ≥ 2. This result is tight, and sothe congestion gap for d-furcated flows is bounded andexactly equal to 1+ 1/(d-1). For the case d=1 (confluent flows), it is known that the congestion gap is unbounded, namely Θ(log n). Thus, allowing single-sink multicommodity network flows to increase their maximum out degree from one to two virtually eliminates this previously observed congestion gap.

We introduce a game theoretic model of network formation in an effort to understand the complex system of business relationships between various Internet entities (e.g., autonomous systems, enterprise networks, residential customers). This system is at the heart of Internet connectivity. In our model we are given a network topology of nodes and links where the nodes (modeling the various Internet entities) act as the players of the game, and links represent potential contracts. Nodes wish to satisfy their demands, which earn potential revenues, but nodes may have to pay (or be paid by) their neighbors for links incident to them. By incorporating some of the qualities of Internet business relationships, we hope that our model has predictive value. Specifically, we assume that contracts are either customer-provider or peering contracts. As often occurs in practice, we also include a mechanism that penalizes nodes if they drop traffic emanating from one of their customers. For a natural objective function, we prove that the price of stability is at most 2. With respect to social welfare, however, the prices of anarchy and stability can both be unbounded, leading us to consider how much we must perturb the system to obtain good stable solutions. We thus focus on the quality of Nash equilibria achievable through centralized incentives; solutions created by an "altruistic entity" (e.g., the government) able to increase individual payouts for successfully routing a particular demand. We show that if every payout is increased by a factor of 2, then there is a Nash equilibrium as good as the original centrally defined social optimum. We also show how to find equilibria efficiently in multicast trees. Finally, we give a characterization of Nash equilibria as flows of utility with certain constraints, which helps to visualize the structure of stable solutions and provides us with useful proof techniques

As wireless access technologies improve in data rates, the problem focus is shifting towards providing adequate backhaul from the wireless access points to the Internet. Existing wired backhaul technologies such as copper wires running at DSL, T1, or T3 speeds can be expensive to install or lease, and are becoming a performance bottleneck as wireless access speeds increase. Longhaul, non-line-of-sight wireless technologies such as WiMAX (802.16) hold the promise of enabling a high speed wireless backhaul as a cost-effective alternative. However, the biggest challenge in building a wireless backhaul is achieving guaranteed performance (throughput and delay) that is typically provided by a wired backhaul. This paper explores the problem of efficiently designing a multihop wireless backhaul to connect multiple wireless access points to a wired gateway. In particular, we provide a generalized link activation framework for scheduling packets over this wireless backhaul, such that any existing wireline scheduling policy can be implemented locally at each node of the wireless backhaul. We also present techniques for determining good interference-free routes within our scheduling framework, given the link rates and cross-link interference information. When a multihop wireline scheduler with worst case delay bounds (such as WFQ or Coordinated EDF) is implemented over the wireless backhaul, we show that our scheduling and routing framework guarantees approximately twice the delay of the corresponding wireline topology. Finally, we present simulation results to demonstrate the low delays achieved using our framework.

Despite improvements in wireless access technologies such as 3G or 802.11x, ubiquitous data access has remained a challenge, mainly due to the lack of inexpensive, pervasive backhaul connections from access points to the Internet. With the recent WiMAX standard for high-speed, non-line-of-sight fixed wireless links, multihop wireless backhauls might now overcome this bottleneck. However an important remaining challenge is to provide rate and delay guarantees for customer connections similar to wired backhauls. We provide several schemes for performing admission control for connections with QoS requirements over a multihop wireless backhaul. This is the first work to address both rate and delay requirements for connections. Our admission control algorithms first construct appropriate tree-based topologies connecting wireless backhaul nodes to a wired gateway and then admit the best subset of connections while respecting their rate and delay requirements. Alternately, we admit all the connections with appropriate degradation of their QoS requirements

Using (WDM) technology, an optical network can route multiple signals simultaneously along a single optical fiber by encoding each signal on its own wavelength. If the network contains places where multiple fibers connect together and signals are allowed to be moved from any of the incoming fibers to any of the outgoing fibers, then the network is said to contain cross-connects. More precisely, a $k_1\,\times\,k_2$ WDM cross-connect has k 1 input fibers and k 2 output fibers. Each of the k 1 input fibers supports the same n 1 input wavelengths and each of the k 2 output fibers supports the same n 2 output wavelengths. Since a signal on input wavelength $\lambda$ can be routed from its input fiber to an output fiber such that it arrives on the output fiber using wavelength $\gamma$, where $\lambda \neq \gamma$, the cross-connect must be capable of performing wavelength conversion. Along any fiber in the cross-connect a device called a wavelength interchanger can be inserted to perform wavelength conversion. In other words if the path of a signal from an input fiber to an output fiber passes through a \wins, then the wavelength of the signal can be changed to any wavelength that is not already in use along the fiber leaving the wavelength interchanger. Given the high cost of \wisns, the overall cost of a \CC{k_1}{k_2} is minimized by reducing the number of \wis in the cross-connect. However, a desirable property for a cross-connect C is for C to always be able to provide a route (and wavelength conversion) for any valid demand from any pair of input and output fibers regardless of the routes of other demands currently routed in C. If C has this capability then it is said to be strictly nonblocking. For most of this paper we consider a demand to be a request for a connection from an input fiber to an output fiber such that the connection starts on a specified input wavelength and leaves the ç on a second specified wavelength. Using this demand model, we consider cross-connects for which $k_1$ is not necessarily equal to $k_2$ and the number $n_1$ of supported input wavelengths can differ from the number $n_2$ of supported output wavelengths. Without loss of generality we assume that $k_1 \leq k_2$ and present a family of \snob \CCns{k_1}{k_2}s that use \Opt \wisns. For the case when $k_1 = k_2=k$ and $n_1 = n_2$, we prove that this is optimal. For çs where $n_1$ is not necessarily equal to $n_2$, we show that if there is at most one wavelength interchanger on any path from an input fiber to an output fiber, \Opt \wis are optimal. Finally, we consider a more flexible demand model where $k_1 = k_2$ but the input and output wavelengths are not specified as part of the demand. We show that $2k-1$ \wis are still necessary for any \snob \CC{k}{k}.

The multi exit discriminator (MED) attribute of the border gateway protocol (BGP) is widely used to implement "cold potato routing" between autonomous systems. However, the use of MED in practice has led to BGP persistent oscillation. The MED oscillation problem has been described with example configurations and complicated, step-by-step evaluation of dynamic route computations performed at multiple routers. Our work presents the first rigorous analysis of the MED oscillation problem. We employ the stable paths problem (SPP) formalism that allows a static analysis of the interaction of routing policies. We give a formal definition of MED induced routing anomalies (MIRA) and show that, in general, they can span multiple autonomous systems. However, if we assume that the BGP configurations between autonomous systems follows a common model based on customer/provider and peer/peer relationships, then we show that the scope of any MIRA is always contained within a single autonomous system. Contrary to widely held assumptions, we show that a MIRA can occur even in a fully meshed IBGP configuration. We also show that a stable BGP routing may actually violate the stated semantics of the MED attribute.

We study the route oscillation problem [16, 19] in the Internal Border Gateway Protocol (I-BGP)[18] when route reflection is used. We propose a formal model of I-BGP and use it to show that even deciding whether an I-BGP configuration with route reflection can converge is an NP-Complete problem. We then propose a modification to I-BGP and show that route reflection cannot cause the modified protocol to diverge. Moreover, we show that the modified protocol converges to the same stable routing configuration regardless of the order in which messages are sent or received.

The Border Gateway Protocol (BGP) has two distinct modes of operation. External BGP (EBGP) exchanges reachability information between autonomous systems, while Internal BGP (IBGP) exchanges external reachability information within an autonomous system. We study several routing anomalies that are unique to IBGP because, unlike EBGP, forwarding paths and signaling paths are not always symmetric. In particular, we focus on anomalies that can cause the protocol to diverge, and those that can cause a router's chosen forwarding path to an egress point to be deflected by another router on that path. Deflections can greatly complicate the debugging of routing problems, and in the worst case multiple deflections can combine to form persistent forwarding loops. We define a correct IBGP configuration to be one that is anomaly free for every possible set of routes sent by neighboring autonomous systems. We show that determination of IBGP configuration correctness is NP-hard. However, we give simple sufficient conditions on network configurations that guarantee correctness.

Dynamic routing protocols such as RIP and OSPF essentially implement distributed algorithms for solving the shortest paths problem. The border gateway protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP does not solve a shortest paths problem since any interdomain protocol is required to allow policy-based metrics to override distance-based metrics and enable autonomous systems to independently define their routing policies with little or no global coordination. It is then natural to ask if BGP can be viewed as a distributed algorithm for solving some fundamental problem. We introduce the stable paths problem and show that BGP can be viewed as a distributed algorithm for solving this problem. Unlike a shortest path tree, such a solution does not represent a global optimum, but rather an equilibrium point in which each node is assigned its local optimum. We study the stable paths problem using a derived structure called a dispute wheel, representing conflicting routing policies at various nodes. We show that if no dispute wheel can be constructed, then there exists a unique solution for the stable paths problem. We define the simple path vector protocol (SPVP), a distributed algorithm for solving the stable paths problem. SPVP is intended to capture the dynamic behavior of BGP at an abstract level. If SPVP converges, then the resulting state corresponds to a stable paths solution. If there is no solution, then SPVP always diverges. In fact, SPVP can even diverge when a solution exists. We show that SPVP will converge to the unique solution of an instance of the stable paths problem if no dispute wheel exists.

The principle that for every document analysis task there exists a mechanism for creating well-defined ground-truth is a widely held tenet. Past experience with standard datasets providing ground-truth for character recognition and page segmentation tasks supports this belief. In the process of attempting to evaluate several table recognition algorithms we have been developing, however, we have uncovered a number of serious hurdles connected with the ground-truthing of tables. This problem may, in fact, be much more difficult than it appears. We present a detailed analysis of why table ground-truthing is so hard, including the notions that there may exist more than one acceptable "truth" and/or incomplete or partial "truths".

While techniques for evaluating the performance of lower-level document analysis tasks such as optical character recognition have gained acceptance in the field, attempts to formalize the problem for higher-level algorithms that incorporate more complex structure have been less successful. We describe an intuitive, easy-to-implement scheme for the problem of performance evaluation when document recognition results are represented in the form of a directed acyclic graph. We present results from two simulation studies based on different graph models and one experiment using a well known page segmentation algorithm to demonstrate the applicability of the approach.

An IP routing protocol is safe if it is guaranteed to converge in the absence of network topology changes. BGP, currently the only interdomain routing protocol employed on the Internet, is not safe in this sense. It may seem that the source of BGP's potential divergence is inherent in the requirements for any interdomain routing protocol-policy-based metrics must be allowed to override distance-based metrics, and each autonomous system must be allowed to independently define its routing policies with little or no global coordination. In this paper we present a simple path vector protocol (SPVP) that captures the underlying semantics of BGP by abstracting away all nonessential details. We then add a dynamically computed attribute to SPVP routing messages, called the route history. Protocol oscillations caused by policy conflicts produce routes whose histories contain cycles. These cycles identify the policy conflicts and the autonomous systems involved. SPVP is made safe by automatically suppressing routes whose histories contain cycles. We discuss how this safe SPVP can be used in the design of a safe BGP.

Article Strictly non-blocking WDM cross-connects for heterogeneous networks Share on Authors: April Rasala MIT Laboratory for Computer Science, Cambridge, MA MIT Laboratory for Computer Science, Cambridge, MAView Profile , Gordon Wilfong Bell Labs, Lucent Technologies, Murray Hill, NJ Bell Labs, Lucent Technologies, Murray Hill, NJView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 514–523https://doi.org/10.1145/335305.335366Online:01 May 2000Publication History 15citation312DownloadsMetricsTotal Citations15Total Downloads312Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The paper describes features and methods for document image comparison and classification at the spatial layout level. The methods are useful for visual similarity based document retrieval as well as fast algorithms for initial document type classification without OCR. A novel feature set called interval encoding is introduced to capture elements of spatial layout. This feature set encodes region layout information in fixed-length vectors which can be used for fast page layout comparison. The paper describes experiments and results to rank-order a set of document pages in terms of their layout similarity to a test document. We also demonstrate the usefulness of the features derived from interval encoding in a hidden Markov model based page layout classification system that is trainable and extendible.

The border gateway protocol, BGP, is currently the only interdomain routing protocol employed on the Internet. As required of any interdomain protocol, BGP allows policy-based metrics to override distance-based metrics and enables each autonomous system to independently define its routing policies with little or no global coordination. Varadhan et al. (1996) have shown that there are collections of routing policies that together are not safe in the sense that they can cause BGP to diverge. That is, an unsafe collection of routing policies can result in some autonomous systems exchanging BGP routing messages indefinitely, without ever converging to a set of stable routes. In this paper we present sufficient conditions on routing policies that guarantee BGP safety. We use a new formalism, called the simple path vector protocol (SPVP), that is designed to capture the underlying semantics of any path vector protocol such as BGP. We identify a certain circular set of relationships between routing policies at various autonomous systems that we call a dispute cycle. We show that systems with no dispute cycles are guaranteed to be safe. While these include systems whose policies are consistent with shortest paths under some link metric, the class of systems with no dispute cycles is strictly larger.

The Border Gateway Protocol (BGP) is the de facto inter-domain routing protocol used to exchange reachability information between Autonomous Systems in the global Internet. BGP is a path-vector protocol that allows each Autonomous System to override distance-based metrics with policy-based metrics when choosing best routes. Varadhan et al. [18] have shown that it is possible for a group of Autonomous Systems to independently define BGP policies that together lead to BGP protocol oscillations that never converge on a stable routing. One approach to addressing this problem is based on static analysis of routing policies to determine if they are safe. We explore the worst-case complexity for convergence-oriented static analysis of BGP routing policies. We present an abstract model of BGP and use it to define several global sanity conditions on routing policies that are related to BGP convergence/divergence. For each condition we show that the complexity of statically checking it is either NP-complete or NP-hard.

We study the problem of determining whether a manufactured disk of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of the manufactured object, compute the thinnest annulus whose outer (or inner, or median) radius is r and that contains all the probe points. Our algorithms run in O(nlogn) time.

An online system for recognizing handwritten symbols from a user specified alphabet is described. The symbols are written on a digitising tablet. When a symbol is subsequently written the system is required to recognize the symbol irrespective of the scale, orientation and position of the written symbol.

Suppose E is a set of labeled points (examples) in some metric space. A subset C of E is said to be a consistent subset ofE if it has the property that for any example e∈E, the label of the closest...

Paths that stay on a given network of line segments except to turn onto one segment from another by following a circular arc are studied. The problem of finding a shortest-length collision-free path of this form for an autonomous vehicle with a bound on its steering angle is considered. A polynomial-time algorithm to modify a given feasible path into a shortest-length path traversing the same sequence of lanes is given. However, if the sequence of lanes to be traversed is not fixed, then the general problem of finding a shortest-length path of the restricted form is shown to be NP-complete.>

Article Free Access Share on The furthest-site geodesic Voronoi diagram Authors: B. Aronov Courant Institute of Mathematical Sciences, NYU Courant Institute of Mathematical Sciences, NYUView Profile , S. Fortune AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile , G. Wilfong AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims SCG '88: Proceedings of the fourth annual symposium on Computational geometryJanuary 1988 Pages 229–240https://doi.org/10.1145/73393.73417Published:06 January 1988Publication History 2citation531DownloadsMetricsTotal Citations2Total Downloads531Last 12 Months25Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Motion planning algorithms have generally dealt with motion in a static environment, or more recently, with motion in an environment that changes in a known manner. We consider the problem of finding collision-free motions in a changeable environment. That is, we wish to find a motion for an object where the object is permitted to move some of the obstacles. In such an environment the final positions of the movable obstacles may or may not be part of the goal. In the case where the final positions of the obstacles are unspecified, the motion planning problem is shown to be NP-hard. An algorithm that runs in Ο(n2logn) time after Ο(n3log2n) preprocessing time is presented when the object to be moved is polygonal and there is only one movable polygonal obstacle in a polygonal environment of complexity Ο(n). In the case where the final positions of the obstacles are specified the general problem is shown to be PSPACE-hard and an algorithm is given when there is one movable obstacle with the same preprocessing time as the previous algorithm but with Ο(n2) query time.

An algorithm for computing a collision-free motion for a vehicle with limited steering range is presented and its running time is analyzed. When given m 'lanes' on which the vehicle is allowed to move in a polygonal environment of complexity n, the algorithm produces a motion with the minimum number of turns between two query placements of the vehicle in time O(m/sup 2/)after O(m/sup 2/(n/sup 2/+log m)) preprocessing. A restricted version of the algorithm has been implemented.>

Article Free Access Share on Planning constrained motion Authors: Steven Fortune AT&T Bell Laboratories, Murray Hill, New Jersey AT&T Bell Laboratories, Murray Hill, New JerseyView Profile , Gordon Wilfong AT&T Bell Laboratories, Murray Hill, New Jersey AT&T Bell Laboratories, Murray Hill, New JerseyView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 445–459https://doi.org/10.1145/62212.62256Published:01 January 1988Publication History 50citation396DownloadsMetricsTotal Citations50Total Downloads396Last 12 Months25Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We study the problem of planning simultaneous motion for two robot arms that are modeled on the Stanford arm. The arms have two degrees of freedom and must move in a workspace, avoiding obstacles and each other. We develop an O(n2logn) algorithm for planning motion of two arms with tips together, and an O(n3) algorithm for independent but synchronized motion. Here n is the total number of walls of the obstacles.

The motion planning problem for multiple objects is studied where an object is a 2-dimensional region whose sides are line segments parallel to the axes of ${\bf R}^2 $ and translations are the only motions allowed. Towards this end we analyze the structure of configuration space, the space of points that correspond to positions of the objects. In particular, we consider CONNECTED, the set of all points in configuration space that correspond to configurations of the objects where the objects form one connected component. We show that CONNECTED consists of faces of various dimensions such that if there is a path in CONNECTED between two 0-dimensional faces (vertices) of CONNECTED then there is a path between them along 1-dimensional faces (edges) of CONNECTED. It is known that if there is a motion between two configurations of CONNECTED then there is a path in CONNECTED between the configurations. Thus the existence of a motion between two vertices of CONNECTED implies a motion corresponding to a path along edges of CONNECTED. Hence the motion planning problem is reduced from a search of a high dimensional space to a graph searching problem. From this result it is shown that motion planning for rectangles in a rectangular boundary is in PSPACE. Since it is known that the problem is PSPACE-hard, we conclude it is a PSPACE-complete problem.