Author name cluster

Athanasios Krontiris

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

ICRA Conference 2016 Conference Paper

Efficiently solving general rearrangement tasks: A fast extension primitive for an incremental sampling-based planner

Athanasios Krontiris
Kostas E. Bekris

Manipulating multiple movable obstacles is a hard problem that involves searching high-dimensional C-spaces. A milestone method for this problem was able to compute solutions for monotone instances. These are problems where every object needs to be transferred at most once to achieve a desired arrangement. The method uses backtracking search to find the order with which objects should be moved. This paper first proposes an approximate but significantly faster alternative for monotone rearrangement instances. The method defines a dependency graph between objects given minimum constraint removal paths (MCR) to transfer each object to its target. From this graph, the approach discovers the order of moving objects by performing topological sorting without backtracking search. The approximation arises from the limitation to consider only MCR paths, which minimize, however, the number of conflicts between objects. To solve non-monotone instances, this primitive is incorporated in a higher-level incremental search algorithm for general rearrangement planning, which operates similar to Bi-RRT. Given a start and a goal object arrangement, tree structures of reachable new arrangements are generated by using the primitive as an expansion procedure. The integrated solution achieves probabilistic completeness for the general non-monotone case and based on simulated experiments it achieves very good success ratios, solution times and path quality relative to alternatives.

Details

SoCS Conference 2015 Conference Paper

Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths

Athanasios Krontiris
Kostas E. Bekris

The typical objective of path planning is to find the shortest feasible path. Many times, however, there may be no solution given the existence of constraints, such as obstacles. In these cases, the minimum constraint removal problem asks for the minimum set of constraints that need to be removed from the state space to find a solution. Unfortunately, minimum constraint removal paths do not exhibit dynamic programming properties, i. e. , subsets of optimum solutions are not necessarily optimal. Thus, searching for such solutions is computationally expensive. This leads to approximate methods, which balance the cost of computing a solution and its quality. This work investigates alternatives in this context and evaluates their performance in terms of such tradeoffs. Solutions that follow a bounded-length approach, i. e. , searching for paths up to a certain length, seem to provide a good balance between minimizing constraints, computational cost and path length.

Details

SoCS Conference 2013 Conference Paper

From Feasibility Tests to Path Planners for Multi-Agent Pathfinding

Athanasios Krontiris
Ryan Luna
Kostas E. Bekris

Multi-agent pathfinding is an important challenge that relates to combinatorial search and has many applications, such as warehouse management, robotics and computer games. Finding an optimal solution is NP-hard and raises scalability issues for optimal solvers. Interestingly, however, it takes linear time to check the feasibility of an instance. These linear-time feasibility tests can be extended to provide path planners but to the best of the authors’ knowledge no such solver has been provided for general graphs. This work first describes a path planner that is inspired by a linear-time feasibility test for multi-agent pathfinding on general graphs. Initial experiments indicated reasonable scalability but worse path quality relative to existing suboptimal solutions. This led to the development of an algorithm that achieves both efficient running time and path quality relative to the alternatives and which finds a solution on available benchmarks. The paper outlines the relation of the final method to the feasibility tests and existing suboptimal planners. Experimental results evaluate the different algorithms, including an optimal solver.

Details

ICRA Conference 2012 Conference Paper

Multi-level formation roadmaps for collision-free dynamic shape changes with non-holonomic teams

Athanasios Krontiris
Sushil J. Louis
Kostas E. Bekris

Teams of robots can utilize formations to accomplish a task, such as maximizing the observability of an environment while maintaining connectivity. In a cluttered space, however, it might be necessary to automatically change formation to avoid obstacles. This work proposes a path planning approach for non-holonomic robots, where a team dynamically switches formations to reach a goal without collisions. The method introduces a multi-level graph, which can be constructed offline. Each level corresponds to a different formation and edges between levels allow for formation transitions. All edges satisfy curvature bounds and clearance requirements from obstacles. During the online phase, the method returns a path for a virtual leader, as well as the points along the path where the team should switch formations. Individual agents can compute their controls using kinematic formation controllers that operate in curvilinear coordinates. The approach guarantees that it is feasible for the agents to follow the trajectory returned. Simulations show that the online cost of the approach is small. The method returns solutions that maximize the maintenance of a desired formation while allowing the team to rearrange its configuration in the presence of obstacles.

Details

ICRA Conference 2011 Conference Paper

General dynamic formations for non-holonomic systems along planar curvilinear coordinates

Athanasios Krontiris
Sushil J. Louis
Kostas E. Bekris

This paper describes a general geometric method for planar formations of non-holonomic systems. The approach directly provides the feasible controls that each individual robot has to execute in order for the team to maintain the formation based on the controls of a reference agent, either a real leader-robot or a virtual one. In order to directly satisfy the non-holonomic constraints, the geometric reasoning takes place in curvilinear coordinates, defined by the curvature of the reference trajectory, instead of the typical rectilinear coordinates. The generality of the approach lies on the ability to define dynamic formations so as to smoothly switch between static ones, where the robots can change both of their relative coordinates as they move, and the ability to acquire a desired formation given an initial random configuration. Furthermore, it is possible to correct errors in the achieved configuration of the vehicles on the fly. Simulated experiments are presented to verify the correctness of the provided derivations.

Details

IROS Conference 2011 Conference Paper

Using minimal communication to improve decentralized conflict resolution for non-holonomic vehicles

Athanasios Krontiris
Kostas E. Bekris

This work considers the problem of decentralized coordination between multiple non-holonomic vehicles, each navigating to a specified goal. By augmenting the Generalized Roundabout Policy (GRP), which guarantees collision avoidance, this paper improves the performance and liveness characteristics for such problems. These gains are achieved by integrating a second hybrid policy with GRP that updates the desired direction for each vehicle based on a dynamic priority scheme. In this scheme, minimalistic communication between vehicles is employed, such that information is periodically exchanged when changes in the high-level operating mode or prioritization occur. This information exchange is taking place only locally and data are exchanged only between neighboring vehicles. Additionally, each agent selects a control using only this local information and rules established by the two underlying hybrid automata. The proposed technique scales well due to its decentralized nature and as the computational complexity depends on the maximum number of vehicles in communication range for a vehicle. This paper presents simulations which show that the proposed approach can solve problems faster than using GRP alone, as well as solve instances in which GRP fails to find a solution, with minimal communication and computational overhead.

Details