An official website of the United States government
In this paper, we adopt a new perspective on the Multi-Agent Path Finding (MAPF) problem and view it as a Constraint Satisfaction Problem (CSP). A variable corresponds to an agent, its domain is the set of all paths from the start vertex to the goal vertex of the agent, and the constraints allow only conflict-free paths for each pair of agents. Although the domains and constraints are only implicitly defined, this new CSP perspective allows us to use successful techniques from CSP search. With the concomitant idea of using matrix computations for calculating the size of the reduced domain of an uninstantiated variable, we apply Dynamic Variable Ordering and Rapid Random Restarts to the MAPF problem. In our experiments, the resulting simple polynomial-time MAPF solver, called Matrix MAPF solver, either outperforms or matches the performance of many state-of-the-art solvers for the MAPF problem and its variants.
more »
« less
Inferring Obstacles and Path Validity from Visibility-Constrained Demonstrations
Many methods in learning from demonstration assume that the demonstrator has knowledge of the full environment. However, in many scenarios, a demonstrator only sees part of the environment and they continuously replan as they gather information. To plan new paths or to reconstruct the environment, we must consider the visibility constraints and replanning process of the demonstrator, which, to our knowledge, has not been done in previous work. We consider the problem of inferring obstacle configurations in a 2D environment from demonstrated paths for a point robot that is capable of seeing in any direction but not through obstacles. Given a set of survey points, which describe where the demonstrator obtains new information, and a candidate path, we con-struct a Constraint Satisfaction Problem (CSP) on a cell decomposition of the environment. We parameterize a set of obstacles corresponding to an assignment from the CSP and sample from the set to find valid environments. We show that there is a probabilistically-complete, yet not entirely tractable, algorithm that can guarantee novel paths in the space are unsafe or possibly safe. We also present an incomplete, but empirically-successful, heuristic-guided algorithm that we apply in our experiments to 1) planning novel paths and 2) recovering a probabilistic representation of the environment.
more »
« less
- Award ID(s):
- 1553873
- PAR ID:
- 10211346
- Date Published:
- Journal Name:
- Workshop on Algorithmic Foundations of Robotics
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We design a parallel algorithm for the Constrained Shortest Path (CSP) problem. The CSP problem is known to be NP-hard and there exists a pseudo-polynomial time sequential algorithm that solves it. To design the parallel algorithm, we extend the techniques used in the design of the Δ-stepping algorithm for the single-source shortest paths problem.more » « less
-
In this paper, we investigate the design of high throughput relay-assisted millimeter-wave (mmWave) backhaul networks in urban areas. Different from most related works, we consider the deployment of dedicated simple mmWave relay devices to help enhance the line-of-sight (LoS) connectivity of the backhaul network in urban areas with abundant obstacles. Given a set of (logical) backhaul links between base stations in the network, we propose an algorithm to find high-throughput LoS paths with relays for all logical links by minimizing interference within and between paths. We also propose methods to modify the backhaul topology to increase the probability of finding high-throughput paths using our algorithm. Extensive simulations, based on a 3-D model of a section of downtown Atlanta, demonstrate that high-throughput topologies, with minimal inter-path and intra-path interference, are feasible in most cases. The analyses also yield some insights on the mmWave backhaul network design problem.more » « less
-
Learning Environment Constraints in Collaborative Robotics: A Decentralized Leader-Follower ApproachIn this paper, we propose a leader-follower hierarchical strategy for two robots collaboratively transporting an object in a partially known environment with obstacles. Both robots sense the local surrounding environment and react to obstacles in their proximity. We consider no explicit communication, so the local environment information and the control actions are not shared between the robots. At any given time step, the leader solves a model predictive control (MPC) problem with its known set of obstacles and plans a feasible trajectory to complete the task. The follower estimates the inputs of the leader and uses a policy to assist the leader while reacting to obstacles in its proximity. The leader infers obstacles in the follower’s vicinity by using the difference between the predicted and the real-time estimated follower control action. A method to switch the leader-follower roles is used to improve the control performance in tight environments. The efficacy of our approach is demonstrated with detailed comparisons to two alternative strategies, where it achieves the highest success rate, while completing the task fastest.more » « less
-
In this paper, we consider the problem of constructing paths using decode and forward (DF) relays for millimeter wave (mmWave) backhaul communications in urban environments. Due to the large number of obstacles in urban environments, line-of-sight (LoS) wireless links, which are necessary for backhaul communication, often do not exist between small-cell base stations. To address this, some earlier works proposed creating multi-hop paths that use mmWave relay nodes with LoS communication between every pair of consecutive nodes to form logical links between base stations. We present algorithms, based on a novel widest-path formulation of the problem, for selecting decode and forward relay node locations in such paths. Our main algorithm is the first polynomial-time algorithm that constructs a relay path with a throughput that is proven to be the maximum possible. We also present variations of this algorithm for constrained problems in which: 1) each possible relay location can host only one relay node, and 2) minimizing the number of hops in the relay path is also an objective. For all of the proposed algorithms, the achievable throughput and numbers of relays are evaluated through simulation based on a 3-D model of a section of downtown Atlanta. The results show that, over a large number of random cases, our algorithm can always find paths with very high throughput using a small number of relays. We also compare and contrast the results with our earlier work that studied the use of amplify-and-forward (AF) relays for the same scenario.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
