Publications:
2009 |
Bekris, K; Tsianos, K; Kavraki, L Safe and Distributed Kinodynamic Replanning for Vehicular Networks Journal Article Mobile Networks and Applications, 14 (3), 2009. @article{distributed_kinodynamic, title = {Safe and Distributed Kinodynamic Replanning for Vehicular Networks}, author = {K Bekris and K Tsianos and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/distributed_kinodynamic.pdf}, year = {2009}, date = {2009-02-01}, journal = {Mobile Networks and Applications}, volume = {14}, number = {3}, chapter = {292-308}, abstract = {This work deals with the problem of planning collision-free motions for multiple communicating vehicles that operate in the same, partially-observable environment in real-time. A challenging aspect of this problem is how to utilize communication so that vehicles do not reach states from which collisions cannot be avoided due to second-order motion constraints. This paper initially shows how it is possible to provide theoretical safety guarantees with a priority-based coordination scheme. Safety means avoiding collisions with obstacles and between vehicles. This notion is also extended to include the retainment of a communication network when the vehicles operate as a networked team. The paper then progresses to extend this safety framework into a fully distributed communication protocol for real-time planning. The proposed algorithm integrates sampling-based motion planners with message-passing protocols for distributed constraint optimization. Each vehicle uses the motion planner to generate candidate feasible trajectories and the message-passing protocol for selecting a safe and compatible trajectory. The existence of such trajectories is guaranteed by the overall approach. The theoretical results have also been experimentally confirmed with a distributed simulator built on a cluster of processors and using applications such as coordinated exploration. Furthermore, experiments show that the distributed protocol has better scalability properties when compared against the priority-based scheme.}, keywords = {}, pubstate = {published}, tppubtype = {article} } This work deals with the problem of planning collision-free motions for multiple communicating vehicles that operate in the same, partially-observable environment in real-time. A challenging aspect of this problem is how to utilize communication so that vehicles do not reach states from which collisions cannot be avoided due to second-order motion constraints. This paper initially shows how it is possible to provide theoretical safety guarantees with a priority-based coordination scheme. Safety means avoiding collisions with obstacles and between vehicles. This notion is also extended to include the retainment of a communication network when the vehicles operate as a networked team. The paper then progresses to extend this safety framework into a fully distributed communication protocol for real-time planning. The proposed algorithm integrates sampling-based motion planners with message-passing protocols for distributed constraint optimization. Each vehicle uses the motion planner to generate candidate feasible trajectories and the message-passing protocol for selecting a safe and compatible trajectory. The existence of such trajectories is guaranteed by the overall approach. The theoretical results have also been experimentally confirmed with a distributed simulator built on a cluster of processors and using applications such as coordinated exploration. Furthermore, experiments show that the distributed protocol has better scalability properties when compared against the priority-based scheme. |
Bekris, K Informed Planning and Safe Distributed Replanning under Physical Constraints PhD Thesis Rice University (Ph.D Thesis), 2009. @phdthesis{Bekris:2009aa, title = {Informed Planning and Safe Distributed Replanning under Physical Constraints}, author = {K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/bekris_thesis.pdf}, year = {2009}, date = {2009-01-01}, volume = {PhD Thesis.}, pages = {148}, address = {Houston, TX}, school = {Rice University (Ph.D Thesis)}, abstract = {Motion planning is a fundamental algorithmic problem that attracts attention because of its importance in many exciting applications, such as controlling robots or virtual agents in simulations and computer games. While there has been great progress over the last decades in solving high-dimensional geometric problems there are still many challenges that limit the capabilities of existing solutions. In particular, it is important to effectively model and plan for systems with complex dynamics and significant drift (kinodynamic planning). An additional requirement is that realistic systems and agents must safely operate in a real-time fashion (replanning), with partial knowledge of their surroundings (partial observability) and despite the presence or in collaboration with other moving agents (distributed planning). This thesis describes techniques that address challenges related to real-time motion planning while focusing on systems with non-trivial dynamics. The first contribution is a new kinodynamic planner, termed Informed Subdivision Tree (IST), that incorporates heuristics to solve motion planning queries more effectively while achieving the theoretical guarantee of probabilistic completeness. The thesis proposes also a general methodology to construct heuristics for kinodynamic planning based on configuration space knowledge through a roadmap-based approach. Then this thesis investigates replanning problems, where a planner is called periodically given a predefined amount of time. In this scenario, safety concerns arise by the presence of both dynamic motion constraints and time limitations. The thesis proposes the framework of Short-Term Safety Replanning (STSR), which achieves safety guarantees in this context while minimizing computational overhead. The final contribution corresponds to an extension of the STSR framework in distributed planning, where multiple agents communicate to safely avoid collisions despite their dynamic constraints. The proposed algorithms are tested on simulated systems with interesting dynamics, including physically simulated systems. Such experiments correspond to the state-of-the-art in terms of system modeling for motion planning. The experiments show that the proposed techniques outperform existing alternatives, where available, and emphasize their computational advantages.}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } Motion planning is a fundamental algorithmic problem that attracts attention because of its importance in many exciting applications, such as controlling robots or virtual agents in simulations and computer games. While there has been great progress over the last decades in solving high-dimensional geometric problems there are still many challenges that limit the capabilities of existing solutions. In particular, it is important to effectively model and plan for systems with complex dynamics and significant drift (kinodynamic planning). An additional requirement is that realistic systems and agents must safely operate in a real-time fashion (replanning), with partial knowledge of their surroundings (partial observability) and despite the presence or in collaboration with other moving agents (distributed planning). This thesis describes techniques that address challenges related to real-time motion planning while focusing on systems with non-trivial dynamics. The first contribution is a new kinodynamic planner, termed Informed Subdivision Tree (IST), that incorporates heuristics to solve motion planning queries more effectively while achieving the theoretical guarantee of probabilistic completeness. The thesis proposes also a general methodology to construct heuristics for kinodynamic planning based on configuration space knowledge through a roadmap-based approach. Then this thesis investigates replanning problems, where a planner is called periodically given a predefined amount of time. In this scenario, safety concerns arise by the presence of both dynamic motion constraints and time limitations. The thesis proposes the framework of Short-Term Safety Replanning (STSR), which achieves safety guarantees in this context while minimizing computational overhead. The final contribution corresponds to an extension of the STSR framework in distributed planning, where multiple agents communicate to safely avoid collisions despite their dynamic constraints. The proposed algorithms are tested on simulated systems with interesting dynamics, including physically simulated systems. Such experiments correspond to the state-of-the-art in terms of system modeling for motion planning. The experiments show that the proposed techniques outperform existing alternatives, where available, and emphasize their computational advantages. |
2008 |
Bekris, K; Kavraki, L Informed and Probabilistically Complete Search for Motion Planning under Differential Constraints Conference First International Symposium on Search Techniques in Artificial Intelligence and Robotics (STAIR), Chicago, IL, 2008. @conference{Bekris:2008aa, title = {Informed and Probabilistically Complete Search for Motion Planning under Differential Constraints}, author = {K Bekris and L Kavraki}, url = {https://cdn.aaai.org/Workshops/2008/WS-08-10/WS08-10-002.pdf}, year = {2008}, date = {2008-07-01}, booktitle = {First International Symposium on Search Techniques in Artificial Intelligence and Robotics (STAIR)}, address = {Chicago, IL}, abstract = {Sampling-based search has been shown effective in motion planning, a hard continuous state-space problem. Motion planning is especially challenging when the robotic system obeys differential constraints, such as an acceleration controlled car that cannot move sideways. Methods that expand trajectory trees in the state space produce feasible solutions for such systems. These planners can be viewed as continuous-space analogs of traditional uninformed search as their goal is to explore the entire state space. In many cases, the search can be focused on the part of the state-space necessary to solve a problem by employing heuristics. This paper proposes an informed framework for tree-based planning that successfully balances greedy with methodical search. The framework allows the use of a broad set of heuristics for goal-directed problem solving, while avoiding scaling issues that appear in continuous space heuristic search. It also employs an appropriate discretization technique for continuous state-space problems, based on an adaptive subdivision scheme. Although greedy in nature, the method provides with probabilistic completeness guarantees for a very general class of planning problems. Experiments on dynamic systems simulated with a physics engine show that the technique outperforms uninformed planners and existing informed variants. In many cases, it also produces better quality paths.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Sampling-based search has been shown effective in motion planning, a hard continuous state-space problem. Motion planning is especially challenging when the robotic system obeys differential constraints, such as an acceleration controlled car that cannot move sideways. Methods that expand trajectory trees in the state space produce feasible solutions for such systems. These planners can be viewed as continuous-space analogs of traditional uninformed search as their goal is to explore the entire state space. In many cases, the search can be focused on the part of the state-space necessary to solve a problem by employing heuristics. This paper proposes an informed framework for tree-based planning that successfully balances greedy with methodical search. The framework allows the use of a broad set of heuristics for goal-directed problem solving, while avoiding scaling issues that appear in continuous space heuristic search. It also employs an appropriate discretization technique for continuous state-space problems, based on an adaptive subdivision scheme. Although greedy in nature, the method provides with probabilistic completeness guarantees for a very general class of planning problems. Experiments on dynamic systems simulated with a physics engine show that the technique outperforms uninformed planners and existing informed variants. In many cases, it also produces better quality paths. |
2007 |
Bekris, K; Tsianos, K; Kavraki, L IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS07), San Diego, CA, 2007. @conference{Bekris:2007aa, title = {A Decentralized Planner That Guarantees the Safety of Communicating Vehicles with Complex Dynamics That Replan Online}, author = {K Bekris and K Tsianos and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/decentralized_safety_communication.pdf}, year = {2007}, date = {2007-10-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS07)}, address = {San Diego, CA}, abstract = {This paper considers the problem of coordinating multiple vehicles with kinodynamic constraints that operate in the same partially-known environment. The vehicles are able to communicate within limited range. Their objective is to avoid collisions between them and with the obstacles, while the vehicles move towards their goals. An important issue of real-time planning for systems with bounded acceleration is that inevitable collision states must also be avoided. The focus of this paper is to guarantee safety despite the dynamic constraints with a decentralized motion planning technique that employs only local information. We propose a coordination framework that allows vehicles to generate and select compatible sets of valid trajectories and prove that this scheme guarantees collision-avoidance in the specified setup. The theoretical results have been also experimentally confirmed with a distributed simulator where each vehicle replans online with a sampling-based, kinodynamic motion planner and uses message-passing to communicate with neighboring agents.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper considers the problem of coordinating multiple vehicles with kinodynamic constraints that operate in the same partially-known environment. The vehicles are able to communicate within limited range. Their objective is to avoid collisions between them and with the obstacles, while the vehicles move towards their goals. An important issue of real-time planning for systems with bounded acceleration is that inevitable collision states must also be avoided. The focus of this paper is to guarantee safety despite the dynamic constraints with a decentralized motion planning technique that employs only local information. We propose a coordination framework that allows vehicles to generate and select compatible sets of valid trajectories and prove that this scheme guarantees collision-avoidance in the specified setup. The theoretical results have been also experimentally confirmed with a distributed simulator where each vehicle replans online with a sampling-based, kinodynamic motion planner and uses message-passing to communicate with neighboring agents. |
Bekris, K; Tsianos, K; Kavraki, L First International Conference on Robot Communication and Coordination (ROBOCOMM 2007), Athens, Greece, 2007. @conference{Bekris:2007ab, title = {A Distributed Protocol for Safe Real-Time Planning of Communicating Vehicles with Second-Order Dynamics}, author = {K Bekris and K Tsianos and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/distributed_safety_communication.pdf}, year = {2007}, date = {2007-10-01}, booktitle = {First International Conference on Robot Communication and Coordination (ROBOCOMM 2007)}, address = {Athens, Greece}, abstract = {This work deals with the problem of planning in real-time, collision-free motions for multiple communicating vehicles that operate in the same, partially-observable environment. A challenging aspect of this problem is how to utilize communication so that vehicles do not reach states from which collisions cannot be avoided due to second-order motion constraints. This paper provides a distributed communication protocol for real-time planning that guarantees collision avoidance with obstacles and between vehicles. It can also allow the retainment of a communication network when the vehicles operate as a networked team. The algorithm is a novel integration of sampling-based motion planners with message-passing protocols for distributed constraint optimization. Each vehicle uses the motion planner to generate candidate feasible trajectories and the message-passing protocol for selecting a safe and compatible trajectory. The existence of such trajectories is guaranteed by the overall approach. Experiments on a distributed simulator built on a cluster of processors confirm the safety properties of the approach in applications such as coordinated exploration. Furthermore, the distributed protocol has better scalability properties when compared against typical priority-based schemes.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This work deals with the problem of planning in real-time, collision-free motions for multiple communicating vehicles that operate in the same, partially-observable environment. A challenging aspect of this problem is how to utilize communication so that vehicles do not reach states from which collisions cannot be avoided due to second-order motion constraints. This paper provides a distributed communication protocol for real-time planning that guarantees collision avoidance with obstacles and between vehicles. It can also allow the retainment of a communication network when the vehicles operate as a networked team. The algorithm is a novel integration of sampling-based motion planners with message-passing protocols for distributed constraint optimization. Each vehicle uses the motion planner to generate candidate feasible trajectories and the message-passing protocol for selecting a safe and compatible trajectory. The existence of such trajectories is guaranteed by the overall approach. Experiments on a distributed simulator built on a cluster of processors confirm the safety properties of the approach in applications such as coordinated exploration. Furthermore, the distributed protocol has better scalability properties when compared against typical priority-based schemes. |
Plaku, E; Bekris, K; Kavraki, L Oops for Motion Planning: An Online, Open-Source, Programming System Conference IEEE International Conference on Robotics and Automation (ICRA07), Rome, Italy, 2007. @conference{Plaku:2007aa, title = {Oops for Motion Planning: An Online, Open-Source, Programming System}, author = {E Plaku and K Bekris and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/oopsmp.pdf}, year = {2007}, date = {2007-04-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA07)}, address = {Rome, Italy}, abstract = {The success of sampling-based motion planners has resulted in a plethora of methods for improving planning components, such as sampling and connection strategies, local planners and collision checking primitives. Although this rapid progress indicates the importance of the motion planning problem and the maturity of the field, it also makes the evaluation of new methods time consuming. We propose that a systems approach is needed for the development and the experimental validation of new motion planners and/or components in existing motion planners. In this paper, we present the Online, Open-source, Programming System for Motion Planning (OOPSMP), a programming infrastructure that provides implementations of various existing algorithms in a modular, object-oriented fashion that is easily extendible. The system is open-source, since a community-based effort better facilitates the development of a common infrastructure and is less prone to errors. We hope that researchers will contribute their optimized implementations of their methods and thus improve the quality of the code available for use. A dynamic web interface and a dynamic linking architecture at the programming level allows users to easily add new planning components, algorithms, benchmarks, and experiment with different parameters. The system allows the direct comparison of new contributions with existing approaches on the same hardware and programming infrastructure.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } The success of sampling-based motion planners has resulted in a plethora of methods for improving planning components, such as sampling and connection strategies, local planners and collision checking primitives. Although this rapid progress indicates the importance of the motion planning problem and the maturity of the field, it also makes the evaluation of new methods time consuming. We propose that a systems approach is needed for the development and the experimental validation of new motion planners and/or components in existing motion planners. In this paper, we present the Online, Open-source, Programming System for Motion Planning (OOPSMP), a programming infrastructure that provides implementations of various existing algorithms in a modular, object-oriented fashion that is easily extendible. The system is open-source, since a community-based effort better facilitates the development of a common infrastructure and is less prone to errors. We hope that researchers will contribute their optimized implementations of their methods and thus improve the quality of the code available for use. A dynamic web interface and a dynamic linking architecture at the programming level allows users to easily add new planning components, algorithms, benchmarks, and experiment with different parameters. The system allows the direct comparison of new contributions with existing approaches on the same hardware and programming infrastructure. |
Bekris, K; Kavraki, L Greedy but Safe Replanning under Kinodynamic Constraints Conference IEEE International Conference on Robotics and Automation (ICRA), Rome, Italy, 2007. @conference{Bekris:2007ac, title = {Greedy but Safe Replanning under Kinodynamic Constraints}, author = {K Bekris and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/greedy_but_safe_0.pdf}, year = {2007}, date = {2007-04-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, address = {Rome, Italy}, abstract = {We consider motion planning problems for a vehicle with kinodynamic constraints, where there is partial knowledge about the environment and replanning is required. We present a new tree-based planner that explicitly deals with kinodynamic constraints and addresses the safety issues when planning under finite computation times, meaning that the vehicle avoids collisions in its evolving configuration space. In order to achieve good performance we incrementally update a tree data-structure by retaining information from previous steps and we bias the search of the planner with a greedy, yet probabilistically complete state space exploration strategy. Moreover, the number of collision checks required to guarantee safety is kept to a minimum. We compare our technique with alternative approaches as a standalone planner and show that it achieves favorable performance when planning with dynamics. We have applied the planner to solve a challenging replanning problem involving the mapping of an unknown workspace with a non-holonomic platform.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We consider motion planning problems for a vehicle with kinodynamic constraints, where there is partial knowledge about the environment and replanning is required. We present a new tree-based planner that explicitly deals with kinodynamic constraints and addresses the safety issues when planning under finite computation times, meaning that the vehicle avoids collisions in its evolving configuration space. In order to achieve good performance we incrementally update a tree data-structure by retaining information from previous steps and we bias the search of the planner with a greedy, yet probabilistically complete state space exploration strategy. Moreover, the number of collision checks required to guarantee safety is kept to a minimum. We compare our technique with alternative approaches as a standalone planner and show that it achieves favorable performance when planning with dynamics. We have applied the planner to solve a challenging replanning problem involving the mapping of an unknown workspace with a non-holonomic platform. |
2005 |
Plaku, E; Bekris, K; Chen, B; Ladd, A; Kavraki, L Sampling-Based Roadmap of Trees for Parallel Motion Planning Journal Article IEEE Transactions on Robotics, 21 (4), 2005. @article{Plaku:2005aa, title = {Sampling-Based Roadmap of Trees for Parallel Motion Planning}, author = {E Plaku and K Bekris and B Chen and A Ladd and L Kavraki}, url = {https://ieeexplore.ieee.org/document/1492476}, year = {2005}, date = {2005-08-01}, journal = {IEEE Transactions on Robotics}, volume = {21}, number = {4}, chapter = {597-608}, abstract = {This paper shows how to effectively combine a sampling-based method primarily designed for multiple-query motion planning [probabilistic roadmap method (PRM)] with sampling-based tree methods primarily designed for single-query motion planning (expansive space trees, rapidly exploring random trees, and others) in a novel planning framework that can be efficiently parallelized. Our planner not only achieves a smooth spectrum between multiple-query and single-query planning, but it combines advantages of both. We present experiments which show that our planner is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of our planner is that it is significantly more decoupled than PRM and sampling-based tree planners. Exploiting this property, we designed and implemented a parallel version of our planner. Our experiments show that our planner distributes well and can easily solve high-dimensional problems that exhaust resources available to single machines and cannot be addressed with existing planners.}, keywords = {}, pubstate = {published}, tppubtype = {article} } This paper shows how to effectively combine a sampling-based method primarily designed for multiple-query motion planning [probabilistic roadmap method (PRM)] with sampling-based tree methods primarily designed for single-query motion planning (expansive space trees, rapidly exploring random trees, and others) in a novel planning framework that can be efficiently parallelized. Our planner not only achieves a smooth spectrum between multiple-query and single-query planning, but it combines advantages of both. We present experiments which show that our planner is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of our planner is that it is significantly more decoupled than PRM and sampling-based tree planners. Exploiting this property, we designed and implemented a parallel version of our planner. Our experiments show that our planner distributes well and can easily solve high-dimensional problems that exhaust resources available to single machines and cannot be addressed with existing planners. |
Argyros, A; Bekris, K; Orphanoudakis, S; Kavraki, L Robot Homing by Exploiting Panoramic Vision Journal Article Autonomous Robots, 19 (1), 2005. @article{Argyros:2005aa, title = {Robot Homing by Exploiting Panoramic Vision}, author = {A Argyros and K Bekris and S Orphanoudakis and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/robot_homing_panoramic.pdf}, year = {2005}, date = {2005-01-01}, journal = {Autonomous Robots}, volume = {19}, number = {1}, chapter = {7-25}, abstract = {We propose a novel, vision-based method for robot homing, the problem of computing a route so that a robot can return to its initial "home" position after the execution of an arbitrary "prior" path. The method assumes that the robot tracks visual features in panoramic views of the environment that it acquires as it moves. By exploiting only angular information regarding the tracked features, a local control strategy moves the robot between two positions, provided that there are at least three features that can be matched in the panoramas acquired at these positions. The strategy is successful when certain geometric constraints on the configuration of the two positions relative to the features are fulfilled. In order to achieve long-range homing, the features' trajectories are organized in a visual memory during the execution of the "prior" path. When homing is initiated, the robot selects Milestone Positions (MPs) on the "prior" path by exploiting information in its visual memory. The MP selection process aims at picking positions that guarantee the success of the local control strategy between two consecutive MPs. The sequence of successive MPs successfully guides the robot even if the visual context in the "home" position is radically different from the visual context at the position where homing was initiated. Experimental results from a prototype implementation of the method demonstrate that homing can be achieved with high accuracy, independent of the distance traveled by the robot. The contribution of this work is that it shows how a complex navigational task such as homing can be accomplished efficiently, robustly and in real-time by exploiting primitive visual cues. Such cues carry implicit information regarding the 3D structure of the environment. Thus, the computation of explicit range information and the existence of a geometric map are not required.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We propose a novel, vision-based method for robot homing, the problem of computing a route so that a robot can return to its initial "home" position after the execution of an arbitrary "prior" path. The method assumes that the robot tracks visual features in panoramic views of the environment that it acquires as it moves. By exploiting only angular information regarding the tracked features, a local control strategy moves the robot between two positions, provided that there are at least three features that can be matched in the panoramas acquired at these positions. The strategy is successful when certain geometric constraints on the configuration of the two positions relative to the features are fulfilled. In order to achieve long-range homing, the features' trajectories are organized in a visual memory during the execution of the "prior" path. When homing is initiated, the robot selects Milestone Positions (MPs) on the "prior" path by exploiting information in its visual memory. The MP selection process aims at picking positions that guarantee the success of the local control strategy between two consecutive MPs. The sequence of successive MPs successfully guides the robot even if the visual context in the "home" position is radically different from the visual context at the position where homing was initiated. Experimental results from a prototype implementation of the method demonstrate that homing can be achieved with high accuracy, independent of the distance traveled by the robot. The contribution of this work is that it shows how a complex navigational task such as homing can be accomplished efficiently, robustly and in real-time by exploiting primitive visual cues. Such cues carry implicit information regarding the 3D structure of the environment. Thus, the computation of explicit range information and the existence of a geometric map are not required. |
2004 |
Bekris, K; Argyros, A; Kavraki, L Angle-Based Methods for Mobile Robot Navigation: Reaching the Entire Plane Conference IEEE International Conference on Robotics and Automation (ICRA04), New Orleans, LA, 2004. @conference{Bekris:2004aa, title = {Angle-Based Methods for Mobile Robot Navigation: Reaching the Entire Plane}, author = {K Bekris and A Argyros and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/angle_based_navigation.pdf}, year = {2004}, date = {2004-04-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA04)}, address = {New Orleans, LA}, abstract = {Popular approaches for mobile robot navigation involve range information and metric maps of the workspace. For many sensors, however, such as cameras and wireless hardware, the angle between two extracted features or beacons is easier to measure. With these sensors' features in mind, this paper initially presents a control law, which allows a robot equipped with an omni-directional sensor to reach a subset of the plane by monitoring the angles of only three landmarks. By analyzing the properties of this law, a second law has been developed that reaches the complementary set of points. The two methods are then combined in a path planning framework that reaches any possible goal configuration in a planar obstacle-free workspace with three landmarks. The proposed framework could be combined with other techniques, such as obstacle avoidance and topological maps, to improve the efficiency of autonomous navigation. Experiments have been conducted on a robotic platform equipped with a panoramic camera that exhibits the effectiveness and accuracy of the proposed techniques. This work provides evidence that navigational tasks can be performed using only a small number of primitive sensor cues and without the explicit computation of range information.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Popular approaches for mobile robot navigation involve range information and metric maps of the workspace. For many sensors, however, such as cameras and wireless hardware, the angle between two extracted features or beacons is easier to measure. With these sensors' features in mind, this paper initially presents a control law, which allows a robot equipped with an omni-directional sensor to reach a subset of the plane by monitoring the angles of only three landmarks. By analyzing the properties of this law, a second law has been developed that reaches the complementary set of points. The two methods are then combined in a path planning framework that reaches any possible goal configuration in a planar obstacle-free workspace with three landmarks. The proposed framework could be combined with other techniques, such as obstacle avoidance and topological maps, to improve the efficiency of autonomous navigation. Experiments have been conducted on a robotic platform equipped with a panoramic camera that exhibits the effectiveness and accuracy of the proposed techniques. This work provides evidence that navigational tasks can be performed using only a small number of primitive sensor cues and without the explicit computation of range information. |
Bekris, K Reactive Range-Free Landmark Navigation without Scene Reconstruction Masters Thesis Rice University (MS Thesis), 2004. @mastersthesis{Bekris:2004ab, title = {Reactive Range-Free Landmark Navigation without Scene Reconstruction}, author = {K Bekris}, url = {https://search.proquest.com/openview/48536c7d69dcbbfbadf38ef6443566e3/}, year = {2004}, date = {2004-02-01}, volume = {MS Thesis.}, address = {Houston, TX}, school = {Rice University (MS Thesis)}, abstract = {Popular approaches for mobile robot navigation involve range information and metric maps. For many sensors, however, such as cameras, the angle between two landmarks is easier to measure. With these sensors' features in mind, this thesis presents an angle-based control law, which allows a robot to reach a subset of the plane by monitoring the bearings of three landmarks. By analyzing this law's properties, a second law has been developed that reaches the complementary set of points. The two methods are then combined in a novel sensor-based path-planning framework that reaches any possible goal in a planar obstacle-free workspace. Experiments have been conducted both on a real robotic platform equipped with a panoramic camera that show the efficiency and accuracy of the proposed techniques. This work provides evidence that navigational tasks can be performed using only a small number of primitive sensor cues and without range information or scene reconstruction.}, keywords = {}, pubstate = {published}, tppubtype = {mastersthesis} } Popular approaches for mobile robot navigation involve range information and metric maps. For many sensors, however, such as cameras, the angle between two landmarks is easier to measure. With these sensors' features in mind, this thesis presents an angle-based control law, which allows a robot to reach a subset of the plane by monitoring the bearings of three landmarks. By analyzing this law's properties, a second law has been developed that reaches the complementary set of points. The two methods are then combined in a novel sensor-based path-planning framework that reaches any possible goal in a planar obstacle-free workspace. Experiments have been conducted both on a real robotic platform equipped with a panoramic camera that show the efficiency and accuracy of the proposed techniques. This work provides evidence that navigational tasks can be performed using only a small number of primitive sensor cues and without range information or scene reconstruction. |
2003 |
Akinc, M; Bekris, K; Chen, B; Ladd, A; Plaku, E; Kavraki, L Probabilistic Roadmaps of Trees for Parallel Computation of Multiple Query Roadmaps Conference Eleventh International Symposium on Robotics Research (ISRR), Sienna, Italy, 2003, (SpringerVerlag, Springer Tracts in Advanced Robotics (STAR), editors D. Paolo and R. Chatila). @conference{Akinc:2003aa, title = {Probabilistic Roadmaps of Trees for Parallel Computation of Multiple Query Roadmaps}, author = {M Akinc and K Bekris and B Chen and A Ladd and E Plaku and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/prt.pdf}, year = {2003}, date = {2003-10-01}, booktitle = {Eleventh International Symposium on Robotics Research (ISRR)}, address = {Sienna, Italy}, abstract = {We propose the combination of techniques that solve multiple queries for motion planning problems with single query planners in a motion planning framework that can be efficiently parallelized. In multiple query motion planning, a data structure is built during a preprocessing phase in order to quickly respond to on-line queries. Alternatively, in single query planning, there is no preprocessing phase and all computations occur during query resolution. This paper shows how to effectively combine a powerful sample-based method primarily designed for multiple query planning (the Probabilistic Roadmap Method - PRM) with sample-based tree methods that were primarily designed for single query planning (such as Expansive Space Trees, Rapidly Exploring Random Trees, and others). Our planner, which we call the Probabilistic Roadmap of Trees (PRT), uses a tree algorithm as a subroutine for PRM. The nodes of the PRM roadmap are now trees. We take advantage of the very powerful sampling schemes of recent tree planners to populate our roadmaps. The combined sampling scheme is in the spirit of the non-uniform sampling and refinement techniques employed in earlier work on PRM. PRT not only achieves a smooth spectrum between multiple query and single query planning but it combines advantages of both. We present experiments which show that PRT is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of PRT is that it is significantly more decoupled than PRM and sample-based tree planners. Using this property, we designed and implemented a parallel version of PRT. Our experiments show that PRT distributes well and can easily solve high dimensional problems that exhaust resources available to single machines.}, note = {SpringerVerlag, Springer Tracts in Advanced Robotics (STAR), editors D. Paolo and R. Chatila}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We propose the combination of techniques that solve multiple queries for motion planning problems with single query planners in a motion planning framework that can be efficiently parallelized. In multiple query motion planning, a data structure is built during a preprocessing phase in order to quickly respond to on-line queries. Alternatively, in single query planning, there is no preprocessing phase and all computations occur during query resolution. This paper shows how to effectively combine a powerful sample-based method primarily designed for multiple query planning (the Probabilistic Roadmap Method - PRM) with sample-based tree methods that were primarily designed for single query planning (such as Expansive Space Trees, Rapidly Exploring Random Trees, and others). Our planner, which we call the Probabilistic Roadmap of Trees (PRT), uses a tree algorithm as a subroutine for PRM. The nodes of the PRM roadmap are now trees. We take advantage of the very powerful sampling schemes of recent tree planners to populate our roadmaps. The combined sampling scheme is in the spirit of the non-uniform sampling and refinement techniques employed in earlier work on PRM. PRT not only achieves a smooth spectrum between multiple query and single query planning but it combines advantages of both. We present experiments which show that PRT is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of PRT is that it is significantly more decoupled than PRM and sample-based tree planners. Using this property, we designed and implemented a parallel version of PRT. Our experiments show that PRT distributes well and can easily solve high dimensional problems that exhaust resources available to single machines. |
Bekris, K; Chen, B; Ladd, A; Plaku, E; Kavraki, L Multiple Query Probabilistic Roadmap Planning Using Single Query Planning Primitives Conference IEEE/RJS International Conference on Intelligent Robots and Systems (IROS03), Las Vegas, NV, 2003. @conference{Bekris:2003aa, title = {Multiple Query Probabilistic Roadmap Planning Using Single Query Planning Primitives}, author = {K Bekris and B Chen and A Ladd and E Plaku and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/srt.pdf}, year = {2003}, date = {2003-10-01}, booktitle = {IEEE/RJS International Conference on Intelligent Robots and Systems (IROS03)}, address = {Las Vegas, NV}, abstract = {We propose the combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method PRM with bidirectional rapidly exploring random trees BIRRT as the local planner. With small modifications to the standard algorithms, we obtain a multiple query planner which is significantly faster and more reliable than its component parts. Our method provides a smooth spectrum between the PRM and BIRRT techniques and obtains the advantages of both. We observed that the performance differences are most notable in planning instances with several rigid non-convex robots in a scene with narrow passages. This planner is in the spirit of non-uniform sampling and refinement techniques used in earlier work on PRM.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We propose the combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method PRM with bidirectional rapidly exploring random trees BIRRT as the local planner. With small modifications to the standard algorithms, we obtain a multiple query planner which is significantly faster and more reliable than its component parts. Our method provides a smooth spectrum between the PRM and BIRRT techniques and obtains the advantages of both. We observed that the performance differences are most notable in planning instances with several rigid non-convex robots in a scene with narrow passages. This planner is in the spirit of non-uniform sampling and refinement techniques used in earlier work on PRM. |
2001 |
Bekris, K; Hatzopoulos, K; Kazazakis, G; Kontolemakis, G; Masvoula, M; Tsivourakis, N; Argyros, A; Trahanias, P Pytheas: An Integrated Robotic System with Autonomous Navigation Capabilities Conference KTISIVIOS Pan Hellenic Conference in Robotics and Automation, Santorini, Greece, 2001. @conference{Bekris:2001aa, title = {Pytheas: An Integrated Robotic System with Autonomous Navigation Capabilities}, author = {K Bekris and K Hatzopoulos and G Kazazakis and G Kontolemakis and M Masvoula and N Tsivourakis and A Argyros and P Trahanias}, url = {http://www.cs.rutgers.edu/~kb572/pubs/pytheas_ktisivios.pdf}, year = {2001}, date = {2001-07-01}, booktitle = {KTISIVIOS Pan Hellenic Conference in Robotics and Automation}, address = {Santorini, Greece}, abstract = {PYTHEAS is an integrated robotic software system that offers advanced navigation capabilities, which include localization, workspace mapping, path planning and tracking and obstacle avoidance. PYTHEAS facilitates mapping of an unknown indoors environment by exploiting information extracted from a laser scanner. Based on this acquired environment representation, the system is able to navigate autonomously in the mapped environment, while, at the same time, avoiding dynamic obstacles such as moving persons, etc. All the required competences are coupled in an integrated system, which can be controlled through a user-friendly interface over the web. Extensive experimental results demonstrate the capability of the developed system to map complicated environments and support navigation in dynamic worlds.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } PYTHEAS is an integrated robotic software system that offers advanced navigation capabilities, which include localization, workspace mapping, path planning and tracking and obstacle avoidance. PYTHEAS facilitates mapping of an unknown indoors environment by exploiting information extracted from a laser scanner. Based on this acquired environment representation, the system is able to navigate autonomously in the mapped environment, while, at the same time, avoiding dynamic obstacles such as moving persons, etc. All the required competences are coupled in an integrated system, which can be controlled through a user-friendly interface over the web. Extensive experimental results demonstrate the capability of the developed system to map complicated environments and support navigation in dynamic worlds. |
Argyros, A; Bekris, K; Orphanoudakis, S Robot Homing Based on Corner Tracking in a Sequence of Panoramic Images Conference Computer Vision and Pattern Recognition Conference (CVPR01), Hawaii, USA, 2001. @conference{Argyros:2001aa, title = {Robot Homing Based on Corner Tracking in a Sequence of Panoramic Images}, author = {A Argyros and K Bekris and S Orphanoudakis}, url = {http://www.cs.rutgers.edu/~kb572/pubs/homing_corner_tracking.pdf}, year = {2001}, date = {2001-01-01}, booktitle = {Computer Vision and Pattern Recognition Conference (CVPR01)}, address = {Hawaii, USA}, abstract = {In robotics, homing can be defined as that behavior which enables a robot to return to its initial (home) position, after traveling a certain distance along an arbitrary path. Odometry has traditionally been used for the implementation of such a behavior, but it has been shown to be an unreliable source of information. In this work, a novel method for visual homing is proposed, based on a panoramic camera. As the robot departs from its initial position, it tracks characteristic features of the environment (corners). As soon as homing is activated, the robot selects intermediate target positions on the original path. These intermediate positions (IPs) are then visited sequentially, until the home position is reached. For the robot to move between two consecutive IPs, it is only required to establish correspondence among at least three corners. This correspondence is obtained through a feature tracking mechanism. The proposed homing scheme is based on the extraction of very low-level sensory information, namely the bearing angles of corners, and has been implemented on a robotic platform. Experimental results show that the proposed scheme achieves homing with a remarkable accuracy, which is not affected by the distance traveled by the robot.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } In robotics, homing can be defined as that behavior which enables a robot to return to its initial (home) position, after traveling a certain distance along an arbitrary path. Odometry has traditionally been used for the implementation of such a behavior, but it has been shown to be an unreliable source of information. In this work, a novel method for visual homing is proposed, based on a panoramic camera. As the robot departs from its initial position, it tracks characteristic features of the environment (corners). As soon as homing is activated, the robot selects intermediate target positions on the original path. These intermediate positions (IPs) are then visited sequentially, until the home position is reached. For the robot to move between two consecutive IPs, it is only required to establish correspondence among at least three corners. This correspondence is obtained through a feature tracking mechanism. The proposed homing scheme is based on the extraction of very low-level sensory information, namely the bearing angles of corners, and has been implemented on a robotic platform. Experimental results show that the proposed scheme achieves homing with a remarkable accuracy, which is not affected by the distance traveled by the robot. |
0000 |
Dobson, A; Moustakides, G; Bekris, K Sampling-based Roadmap Planners are Probably Near-Optimal after Finite Computation Journal Article CoRR, abs/1404.2166 , 0000. @article{Dobson:2014ac, title = {Sampling-based Roadmap Planners are Probably Near-Optimal after Finite Computation}, author = {A Dobson and G Moustakides and K Bekris}, url = {http://arxiv.org/abs/1404.2166}, journal = {CoRR}, volume = {abs/1404.2166}, abstract = {Sampling-based motion planners have proven to be efficient solutions to a variety of high-dimensional, geometrically complex motion planning problems with applications in several domains. The traditional view of these approaches is that they solve challenges efficiently by giving up formal guarantees and instead attain asymptotic properties in terms of completeness and optimality. Recent work has argued based on Monte Carlo experiments that these approaches also exhibit desirable probabilistic properties in terms of completeness and optimality after finite computation. The current paper formalizes these guarantees. It proves a formal bound on the probability that solutions returned by asymptotically optimal roadmap-based methods (e.g., PRM*) are within a bound of the optimal path length I* with clearance epsilon after a finite iteration n. This bound has the form P(|In - I* | łeq deltaI*) łeq Psuccess, where delta is an error term for the length a path in the PRM* graph, In. This bound is proven for general dimension Euclidean spaces and evaluated in simulation. A discussion on how this bound can be used in practice, as well as bounds for sparse roadmaps are also provided.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Sampling-based motion planners have proven to be efficient solutions to a variety of high-dimensional, geometrically complex motion planning problems with applications in several domains. The traditional view of these approaches is that they solve challenges efficiently by giving up formal guarantees and instead attain asymptotic properties in terms of completeness and optimality. Recent work has argued based on Monte Carlo experiments that these approaches also exhibit desirable probabilistic properties in terms of completeness and optimality after finite computation. The current paper formalizes these guarantees. It proves a formal bound on the probability that solutions returned by asymptotically optimal roadmap-based methods (e.g., PRM*) are within a bound of the optimal path length I* with clearance epsilon after a finite iteration n. This bound has the form P(|In - I* | łeq deltaI*) łeq Psuccess, where delta is an error term for the length a path in the PRM* graph, In. This bound is proven for general dimension Euclidean spaces and evaluated in simulation. A discussion on how this bound can be used in practice, as well as bounds for sparse roadmaps are also provided. |