Co-robots Control Dynamics Human robot interaction Learning Legible paths Manipulation Manipulator modeling Multi-Robot Planning Pose Estimation Rearrangement Robot Perception simulation Sociotechnological Systems tensegrity Topology
2010 |
Apostolopoulos, I; Fallah, N; Folmer, E; Bekris, K E Feasibility of Interactive Localization and Navigation of People with Visual Impairments Conference 11th IEEE Intelligent Autonomous Systems (IAS-10) Conference, Ottawa, Canada, 2010. Abstract | Links | BibTeX | Tags: @conference{apostolopoulos2010feasibility-of-, title = {Feasibility of Interactive Localization and Navigation of People with Visual Impairments}, author = {I Apostolopoulos and N Fallah and E Folmer and K E Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/navatar_feasibility.pdf}, year = {2010}, date = {2010-08-01}, booktitle = {11th IEEE Intelligent Autonomous Systems (IAS-10) Conference}, address = {Ottawa, Canada}, abstract = {Indoor localization and navigation systems for individuals who are visually impaired (VI) typically rely upon expensive physical augmentation of the environment or expensive sensing equipment. This is the reason why only few such systems have been implemented. This work conducts a feasibility study of whether it is possible to localize and guide the navigation of people with VI using inexpensive sensors, such as compasses and pedometers. These sensors are already widely available in portable devices such as smart phones. The proposed approach takes advantage of active interaction between the autonomous intelligent system and the human user and employs the map of the world as a prior. Experiments are employed to study what kind of instructions are most succesful in assisting human users to reach their destination. These experiments also show that the application of Bayesian localization tools can also provide sufficient localization accuracy, while achieving real-time operation, despite the minimalistic, noisy nature of the available information and the limited computational resources available on smart phones. This line of research opens the door to many exciting new applications for methods from robotics in the area of human-centered intelligent systems.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Indoor localization and navigation systems for individuals who are visually impaired (VI) typically rely upon expensive physical augmentation of the environment or expensive sensing equipment. This is the reason why only few such systems have been implemented. This work conducts a feasibility study of whether it is possible to localize and guide the navigation of people with VI using inexpensive sensors, such as compasses and pedometers. These sensors are already widely available in portable devices such as smart phones. The proposed approach takes advantage of active interaction between the autonomous intelligent system and the human user and employs the map of the world as a prior. Experiments are employed to study what kind of instructions are most succesful in assisting human users to reach their destination. These experiments also show that the application of Bayesian localization tools can also provide sufficient localization accuracy, while achieving real-time operation, despite the minimalistic, noisy nature of the available information and the limited computational resources available on smart phones. This line of research opens the door to many exciting new applications for methods from robotics in the area of human-centered intelligent systems. |
Luna, R; Oyama, A; Bekris, K E Network-Guided Multi-Robot Path Planning for Resource-Constrained Planetary Rovers Conference 10th International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS 2010), Sapporo, Japan, 2010. Abstract | Links | BibTeX | Tags: @conference{Luna2010Network-Guided-, title = {Network-Guided Multi-Robot Path Planning for Resource-Constrained Planetary Rovers}, author = {R Luna and A Oyama and K E Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/network_coordination.pdf}, year = {2010}, date = {2010-08-01}, booktitle = {10th International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS 2010)}, address = {Sapporo, Japan}, abstract = {Planetary exploration can benefit by the presence of multiple robots, which must be able to coordinate their paths and avoid collisions. This work proposes the use of a wireless network for the high-level path planning ofmultiple planetary rovers. In this setup, robots receive commands from the network nodes so as to maneuver between locations. Thus, robots can focus on tasks such as local obstacle avoidance and localization. This is desirable in space applications where robots are resource-constrained. Towards this objective, this paper presents a distributed path planning algorithm that is executed on the network nodes and provides collision-free paths for the robots on a precomputed roadmap. The method also aims to minimize the occurence of deadlocks and the time it takes for each robot to reach its goal. The approach follows a distributed constraint optimization formulation that lends itself to a decentralized, message-passing solution that is appropriate for network-guided navigation. Simulations are employed to evaluate the methodtextquoterights scalability and computational cost, as well as the quality of the resulting paths.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Planetary exploration can benefit by the presence of multiple robots, which must be able to coordinate their paths and avoid collisions. This work proposes the use of a wireless network for the high-level path planning ofmultiple planetary rovers. In this setup, robots receive commands from the network nodes so as to maneuver between locations. Thus, robots can focus on tasks such as local obstacle avoidance and localization. This is desirable in space applications where robots are resource-constrained. Towards this objective, this paper presents a distributed path planning algorithm that is executed on the network nodes and provides collision-free paths for the robots on a precomputed roadmap. The method also aims to minimize the occurence of deadlocks and the time it takes for each robot to reach its goal. The approach follows a distributed constraint optimization formulation that lends itself to a decentralized, message-passing solution that is appropriate for network-guided navigation. Simulations are employed to evaluate the methodtextquoterights scalability and computational cost, as well as the quality of the resulting paths. |
Bekris, K E Anchorage, AK, 2010. Abstract | Links | BibTeX | Tags: @workshop{Bekris2010Avoiding-Inevit, title = {Avoiding Inevitable Collision States: Safety and Computational Efficiency in Replanning with Sampling-based Algorithms}, author = {K E Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/ics_tradeoffs.pdf}, year = {2010}, date = {2010-05-01}, address = {Anchorage, AK}, abstract = {Safety concerns arise when planning for systems with dynamics among moving obstacles, where a collision-free trajectory leads to an Inevitable Collision State (ICS). Identifying whether a state is ICS, however, is computationally challenging. This has led to approximations, varying from conservative schemes, which never characterize an ICS as a safe state, to schemes with weaker guarantees but fast online resolution of an ICS query. The computational cost of the approach is critical in problems that require replanning. This report presents various alternatives for identifying whether a state is ICS from the related literature. It also discusses different ways for integrating such schemes with sampling-based planners in safe replanning frameworks so as to reduce the computational overhead of avoiding ICS.}, keywords = {}, pubstate = {published}, tppubtype = {workshop} } Safety concerns arise when planning for systems with dynamics among moving obstacles, where a collision-free trajectory leads to an Inevitable Collision State (ICS). Identifying whether a state is ICS, however, is computationally challenging. This has led to approximations, varying from conservative schemes, which never characterize an ICS as a safe state, to schemes with weaker guarantees but fast online resolution of an ICS query. The computational cost of the approach is critical in problems that require replanning. This report presents various alternatives for identifying whether a state is ICS from the related literature. It also discusses different ways for integrating such schemes with sampling-based planners in safe replanning frameworks so as to reduce the computational overhead of avoiding ICS. |
Li, Y; Bekris, K E Balancing State-Space Coverage in Planning with Dynamics Conference IEEE International Conference on Robotics and Automation (ICRA10), Anchorage, AK, 2010. Abstract | Links | BibTeX | Tags: @conference{balancing_statespace_coverage, title = {Balancing State-Space Coverage in Planning with Dynamics}, author = {Y Li and K E Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/balancing_statespace_coverage.pdf}, year = {2010}, date = {2010-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA10)}, address = {Anchorage, AK}, abstract = {Sampling-based kinodynamic planners, such as the popular RRT algorithm, have been proposed as promising solutions to planning for systems with dynamics. Nevertheless, complex systems often raise significant challenges. In particular, the state-space exploration of sampling-based tree planners can be heavily biased towards a specific direction due to the presence of dynamics and underactuation. The premise of this paper is that it is possible to use statistical tools to learn quickly the effects of the constraints in the algorithmtextquoterights state-space exploration during a training session. Then during the online operation of the algorithm, this information can be utilized so as to counter the undesirable bias due to the dynamics by appropriately adapting the control propagation step. The resulting method achieves a more balanced exploration of the state-space, resulting in faster solutions to planning challenges. The paper provides proof of concept experiments comparing against and improving upon the standard RRT using MATLAB simulations for (a) swinging up different versions of a 3-link Acrobot system with dynamics and (b) a second-order car-like system with significant drift.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Sampling-based kinodynamic planners, such as the popular RRT algorithm, have been proposed as promising solutions to planning for systems with dynamics. Nevertheless, complex systems often raise significant challenges. In particular, the state-space exploration of sampling-based tree planners can be heavily biased towards a specific direction due to the presence of dynamics and underactuation. The premise of this paper is that it is possible to use statistical tools to learn quickly the effects of the constraints in the algorithmtextquoterights state-space exploration during a training session. Then during the online operation of the algorithm, this information can be utilized so as to counter the undesirable bias due to the dynamics by appropriately adapting the control propagation step. The resulting method achieves a more balanced exploration of the state-space, resulting in faster solutions to planning challenges. The paper provides proof of concept experiments comparing against and improving upon the standard RRT using MATLAB simulations for (a) swinging up different versions of a 3-link Acrobot system with dynamics and (b) a second-order car-like system with significant drift. |
2009 |
Bekris, K E; Tsianos, K; Kavraki, L E Safe and Distributed Kinodynamic Replanning for Vehicular Networks Journal Article Mobile Networks and Applications, 14 (3), 2009. Abstract | Links | BibTeX | Tags: @article{distributed_kinodynamic, title = {Safe and Distributed Kinodynamic Replanning for Vehicular Networks}, author = {K E Bekris and K Tsianos and L E 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 E Informed Planning and Safe Distributed Replanning under Physical Constraints PhD Thesis Rice University (Ph.D Thesis), 2009. Abstract | Links | BibTeX | Tags: @phdthesis{bekris_phd, title = {Informed Planning and Safe Distributed Replanning under Physical Constraints}, author = {K E 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 E; Kavraki, L E 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. Abstract | Links | BibTeX | Tags: @conference{informed_planning_dynamics, title = {Informed and Probabilistically Complete Search for Motion Planning under Differential Constraints}, author = {K E Bekris and L E Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/informed_planning_dynamics.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 E; Tsianos, K; Kavraki, L E IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS07), San Diego, CA, 2007. Abstract | Links | BibTeX | Tags: @conference{decentralized_safety_communication, title = {A decentralized planner that guarantees the safety of communicating vehicles with complex dynamics that replan online}, author = {K E Bekris and K Tsianos and L E 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 E; Tsianos, K; Kavraki, L E First International Conference on Robot Communication and Coordination (ROBOCOMM 2007), Athens, Greece, 2007. Abstract | Links | BibTeX | Tags: @conference{distributed_safety_communication, title = {A Distributed Protocol for Safe Real-Time Planning of Communicating Vehicles with Second-Order Dynamics}, author = {K E Bekris and K Tsianos and L E 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. |
Bekris, K E; Kavraki, L E Greedy but Safe Replanning under Kinodynamic Constraints Conference IEEE International Conference on Robotics and Automation (ICRA07), Rome, Italy, 2007. Abstract | Links | BibTeX | Tags: @conference{greedy_but_safe, title = {Greedy but Safe Replanning under Kinodynamic Constraints}, author = {K E Bekris and L E 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 (ICRA07)}, 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. |
Plaku, E; Bekris, K E; Kavraki, L E OOPS for Motion Planning: An Online, Open-Source, Programming System Conference IEEE International Conference on Robotics and Automation (ICRA07), Rome, Italy, 2007. Abstract | Links | BibTeX | Tags: @conference{oopsmp, title = {OOPS for Motion Planning: An Online, Open-Source, Programming System}, author = {E Plaku and K E Bekris and L E 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. |
2006 |
Bekris, K E; Glick, M; Kavraki, L E Evaluation of Algorithms for Bearing-Only SLAM Conference IEEE International Conference on Robotics and Automation (ICRA06), Orlando, FL, 2006. Abstract | Links | BibTeX | Tags: @conference{bearing_only_slam, title = {Evaluation of Algorithms for Bearing-Only SLAM}, author = {K E Bekris and M Glick and L E Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/bearing_only_slam.pdf}, year = {2006}, date = {2006-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA06)}, address = {Orlando, FL}, abstract = {An important milestone for building affordable robots that can become widely popular is to address robustly the Simultaneous Localization and Mapping (SLAM) problem with inexpensive, off-the-shelf sensors, such as monocular cameras. These sensors, however, impose significant challenges on SLAM procedures because they provide only bearing data related to environmental landmarks. This paper starts by providing an extensive comparison of different techniques for bearing-only SLAM in terms of robustness under different noise models, landmark densities and robot paths. We have experimented in a simulated environment with a variety of existing online algorithms including Rao-Blackwellized Particle Filters (RBPFs). Our experiments suggest that RB-PFs are more robust compared to other existing methods and run considerably faster. Nevertheless, their performance suffers in the presence of outliers. In order to overcome this limitation we proceed to propose an augmentation of RB-PFs with: (a) Gaussian Sum Filters for landmark initialization and (b) an online, unsupervised outlier rejection policy. This framework exhibits impressive robustness and efficiency even in the presence of outliers.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } An important milestone for building affordable robots that can become widely popular is to address robustly the Simultaneous Localization and Mapping (SLAM) problem with inexpensive, off-the-shelf sensors, such as monocular cameras. These sensors, however, impose significant challenges on SLAM procedures because they provide only bearing data related to environmental landmarks. This paper starts by providing an extensive comparison of different techniques for bearing-only SLAM in terms of robustness under different noise models, landmark densities and robot paths. We have experimented in a simulated environment with a variety of existing online algorithms including Rao-Blackwellized Particle Filters (RBPFs). Our experiments suggest that RB-PFs are more robust compared to other existing methods and run considerably faster. Nevertheless, their performance suffers in the presence of outliers. In order to overcome this limitation we proceed to propose an augmentation of RB-PFs with: (a) Gaussian Sum Filters for landmark initialization and (b) an online, unsupervised outlier rejection policy. This framework exhibits impressive robustness and efficiency even in the presence of outliers. |
Bekris, K E; Argyros, A A; Kavraki, L E Exploiting Panoramic Vision for Angle-Based Robot Homing Book Chapter Lecture Notes in Computer Science, 33 , Springer, 2006. Abstract | Links | BibTeX | Tags: @inbook{omnidirectional_homing, title = {Exploiting Panoramic Vision for Angle-Based Robot Homing}, author = {K E Bekris and A A Argyros and L E Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/omnidirectional_homing.pdf}, year = {2006}, date = {2006-01-01}, booktitle = {Lecture Notes in Computer Science}, volume = {33}, publisher = {Springer}, organization = {Springer}, abstract = {Omni-directional vision allows for the development of techniques for mobile robot navigation that have minimum perceptual requirements. In this work, we focus on robot navigation algorithms that do not require range information or metric maps of the environment. More specifically, we present a homing strategy that enables a robot to return to its home position after executing a long path. The proposed strategy relies on measuring the angle between pairs of features extracted from panoramic images, which can be achieved accurately and robustly. In the heart of the proposed homing strategy lies a novel, local control law that enables a robot to reach any position on the plane by exploiting the bearings of at least three landmarks of unknown position, without making assumptions regarding the robottextquoterights orientation and without making use of a compass. This control law is the result of the unification of two other local control laws which guide the robot by monitoring the bearing of landmarks and which are able to reach complementary sets of goal positions on the plane. Long-range homing is then realized through the systematic application of the unified control law between automatically extracted milestone positions connecting the robottextquoterights current position to the home position. Experimental results, conducted both in a simulated environment and on a robotic platform equipped with a panoramic camera validate the employed local control laws as well as the overall homing strategy. Moreover, they show that panoramic vision can assist in simplifying the perceptual processes required to support robust and accurate homing behaviors.}, keywords = {}, pubstate = {published}, tppubtype = {inbook} } Omni-directional vision allows for the development of techniques for mobile robot navigation that have minimum perceptual requirements. In this work, we focus on robot navigation algorithms that do not require range information or metric maps of the environment. More specifically, we present a homing strategy that enables a robot to return to its home position after executing a long path. The proposed strategy relies on measuring the angle between pairs of features extracted from panoramic images, which can be achieved accurately and robustly. In the heart of the proposed homing strategy lies a novel, local control law that enables a robot to reach any position on the plane by exploiting the bearings of at least three landmarks of unknown position, without making assumptions regarding the robottextquoterights orientation and without making use of a compass. This control law is the result of the unification of two other local control laws which guide the robot by monitoring the bearing of landmarks and which are able to reach complementary sets of goal positions on the plane. Long-range homing is then realized through the systematic application of the unified control law between automatically extracted milestone positions connecting the robottextquoterights current position to the home position. Experimental results, conducted both in a simulated environment and on a robotic platform equipped with a panoramic camera validate the employed local control laws as well as the overall homing strategy. Moreover, they show that panoramic vision can assist in simplifying the perceptual processes required to support robust and accurate homing behaviors. |
2005 |
Plaku, E; Bekris, K E; Chen, B Y; Ladd, A M; Kavraki, L E Sampling-based Roadmap of Trees for Parallel Motion Planning Journal Article IEEE Transactions on Robotics, 21 (4), 2005. Abstract | Links | BibTeX | Tags: @article{sampling_based_roadmap_of_trees, title = {Sampling-based Roadmap of Trees for Parallel Motion Planning}, author = {E Plaku and K E Bekris and B Y Chen and A M Ladd and L E Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/sampling_based_roadmap_of_trees.pdf}, 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 A; Bekris, K E; Orphanoudakis, S C; Kavraki, L E Robot homing by exploiting panoramic vision Journal Article Autonomous Robots, 19 (1), 2005. Abstract | Links | BibTeX | Tags: @article{robot_homing_panoramic, title = {Robot homing by exploiting panoramic vision}, author = {A A Argyros and K E Bekris and S C Orphanoudakis and L E Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/robot_homing_panoramic.pdf}, year = {2005}, date = {2005-07-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 textquotedbllefthometextquotedblright position after the execution of an arbitrary textquotedblleftpriortextquotedblright 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 featurestextquoteright trajectories are organized in a visual memory during the execution of the textquotedblleftpriortextquotedblright path. When homing is initiated, the robot selects Milestone Positions (MPs) on the textquotedblleftpriortextquotedblright 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 textquotedbllefthometextquotedblright 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 textquotedbllefthometextquotedblright position after the execution of an arbitrary textquotedblleftpriortextquotedblright 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 featurestextquoteright trajectories are organized in a visual memory during the execution of the textquotedblleftpriortextquotedblright path. When homing is initiated, the robot selects Milestone Positions (MPs) on the textquotedblleftpriortextquotedblright 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 textquotedbllefthometextquotedblright 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. |
Ladd, A M; Bekris, K E; Rudys, A; Marceau, G; Kavraki, L E; Wallach, D S Robotics-based Location Sensing using Wireless Ethernet Journal Article Wireless Networks (The Journal of Mobile Communication, Computation and Information), 11 (1-2), 2005. Abstract | Links | BibTeX | Tags: @article{wireless_localization, title = {Robotics-based Location Sensing using Wireless Ethernet}, author = {A M Ladd and K E Bekris and A Rudys and G Marceau and L E Kavraki and D S Wallach}, url = {http://dl.acm.org/citation.cfm?doid=570645.570674}, year = {2005}, date = {2005-01-01}, journal = {Wireless Networks (The Journal of Mobile Communication, Computation and Information)}, volume = {11}, number = {1-2}, chapter = {189-204}, abstract = {A key subproblem in the construction of location-aware systems is the determination of the position of a mobile device. This article describes the design, implementation and analysis of a system for determining position inside a building from measured RF signal strengths of packets on an IEEE 802.11b wireless Ethernet network. Previous approaches to location-awareness with RF signals have been severely hampered by non-Gaussian signals, noise, and complex correlations due to multi-path effects, interference and absorption. The design of our system begins with the observation that determining position from complex, noisy and non-Gaussian signals is a well studied problem in the field of robotics. Using only off-the-shelf hardware, we achieve robust position estimation to within a meter in our experimental context and after adequate training of our system. We can also coarsely determine our orientation and can track our position as we move. Our results show that we can localize a stationary device to within 1.5 meters over 80% of the time and track a moving device to within 1 meter over 50% of the time. Both localization and tracking run in real-time. By applying recent advances in probabilistic inference of position and sensor fusion from noisy signals, we show that the RF emissions from base stations as measured by off-the-shelf wireless Ethernet cards are sufficiently rich in information to permit a mobile device to reliably track its location.}, keywords = {}, pubstate = {published}, tppubtype = {article} } A key subproblem in the construction of location-aware systems is the determination of the position of a mobile device. This article describes the design, implementation and analysis of a system for determining position inside a building from measured RF signal strengths of packets on an IEEE 802.11b wireless Ethernet network. Previous approaches to location-awareness with RF signals have been severely hampered by non-Gaussian signals, noise, and complex correlations due to multi-path effects, interference and absorption. The design of our system begins with the observation that determining position from complex, noisy and non-Gaussian signals is a well studied problem in the field of robotics. Using only off-the-shelf hardware, we achieve robust position estimation to within a meter in our experimental context and after adequate training of our system. We can also coarsely determine our orientation and can track our position as we move. Our results show that we can localize a stationary device to within 1.5 meters over 80% of the time and track a moving device to within 1 meter over 50% of the time. Both localization and tracking run in real-time. By applying recent advances in probabilistic inference of position and sensor fusion from noisy signals, we show that the RF emissions from base stations as measured by off-the-shelf wireless Ethernet cards are sufficiently rich in information to permit a mobile device to reliably track its location. |
2004 |
Ladd, A M; Bekris, K E; Rudys, A; Kavraki, L E; Wallach, D S On the feasibility of Using Wireless Ethernet for Indoor Localization Journal Article IEEE Transactions on Robotics and Automation (TRA), 20 (3), 2004. Abstract | Links | BibTeX | Tags: @article{wireless_localization_feasibility, title = {On the feasibility of Using Wireless Ethernet for Indoor Localization}, author = {A M Ladd and K E Bekris and A Rudys and L E Kavraki and D S Wallach}, url = {http://www.cs.rutgers.edu/~kb572/pubs/wireless_localization_feasibility.pdf}, year = {2004}, date = {2004-06-01}, journal = {IEEE Transactions on Robotics and Automation (TRA)}, volume = {20}, number = {3}, chapter = {555-559}, abstract = {IEEE 802.11b wireless Ethernet is becoming the standard for indoor wireless communication. This paper proposes the use of measured signal strength of Ethernet packets as a sensor for a localization system. We demonstrate that off-the-shelf hardware can accurately be used for location sensing and real-time tracking by applying a Bayesian localization framework.}, keywords = {}, pubstate = {published}, tppubtype = {article} } IEEE 802.11b wireless Ethernet is becoming the standard for indoor wireless communication. This paper proposes the use of measured signal strength of Ethernet packets as a sensor for a localization system. We demonstrate that off-the-shelf hardware can accurately be used for location sensing and real-time tracking by applying a Bayesian localization framework. |
Bekris, K E; Argyros, A A; Kavraki, L E Angle-Based Methods for Mobile Robot Navigation: Reaching the Entire Plane Conference IEEE International Conference on Robotics and Automation (ICRA04), New Orleans, LA, 2004. Abstract | Links | BibTeX | Tags: @conference{angle_based_navigation, title = {Angle-Based Methods for Mobile Robot Navigation: Reaching the Entire Plane}, author = {K E Bekris and A A Argyros and L E 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 sensorstextquoteright 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 sensorstextquoteright 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 E Reactive Range-Free Landmark Navigation without Scene Reconstruction Masters Thesis Rice University (MS Thesis), 2004. @mastersthesis{bekris_MSThesis, title = {Reactive Range-Free Landmark Navigation without Scene Reconstruction}, author = {K E Bekris}, 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 sensorstextquoteright 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 lawtextquoterights 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 sensorstextquoteright 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 lawtextquoterights 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 |
Bekris, K E; Chen, B Y; Ladd, A M; Plaku, E; Kavraki, L E 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. Abstract | Links | BibTeX | Tags: @conference{srt, title = {Multiple Query Probabilistic Roadmap Planning Using Single Query Planning Primitives}, author = {K E Bekris and B Y Chen and A M Ladd and E Plaku and L E 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. |
Akinc, M; Bekris, K E; Chen, B Y; Ladd, A M; Plaku, E; Kavraki, L E 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). Abstract | Links | BibTeX | Tags: @conference{prt, title = {Probabilistic Roadmaps of Trees for Parallel Computation of Multiple Query Roadmaps}, author = {M Akinc and K E Bekris and B Y Chen and A M Ladd and E Plaku and L E 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. |
2002 |
Ladd, A M; Bekris, K E; Rudys, A; Marceau, G; Kavraki, L E; Wallach, D S Robotics-Based Location Sensing using Wireless Ethernet Conference Eight ACM International Conference on Mobile Computing and Networking (MOBICOM 2002), ACM Press ACM Press, Atlanta, GE, 2002. Abstract | Links | BibTeX | Tags: @conference{robotics_based_location_sensing, title = {Robotics-Based Location Sensing using Wireless Ethernet}, author = {A M Ladd and K E Bekris and A Rudys and G Marceau and L E Kavraki and D S Wallach}, url = {http://www.cs.rutgers.edu/~kb572/pubs/robotics_based_location_sensing.pdf}, year = {2002}, date = {2002-09-01}, booktitle = {Eight ACM International Conference on Mobile Computing and Networking (MOBICOM 2002)}, publisher = {ACM Press}, address = {Atlanta, GE}, organization = {ACM Press}, abstract = {A key subproblem in the construction of location-aware systems is the determination of the position of a mobile device. This paper describes the design, implementation and analysis of a system for determining position inside a building from measured RF signal strengths of packets on an IEEE 802.11b wireless Ethernet network. Previous approaches to location-awareness with RF signals have been severely hampered by non-linearity, noise and complex correlations due to multi-path effects, interference and absorption. The design of our system begins with the observation that determining position from complex, noisy and non-linear signals is a well-studied problem in the field of robotics. Using only off-the-shelf hardware, we achieve robust position estimation to within a meter in our experimental context and after adequate training of our system. We can also coarsely determine our orientation and can track our position as we move. By applying recent advances in probabilistic inference of position and sensor fusion from noisy signals, we show that the RF emissions from base stations as measured by off-the-shelf wireless Ethernet cards are sufficiently rich in information to permit a mobile device to reliably track its location.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } A key subproblem in the construction of location-aware systems is the determination of the position of a mobile device. This paper describes the design, implementation and analysis of a system for determining position inside a building from measured RF signal strengths of packets on an IEEE 802.11b wireless Ethernet network. Previous approaches to location-awareness with RF signals have been severely hampered by non-linearity, noise and complex correlations due to multi-path effects, interference and absorption. The design of our system begins with the observation that determining position from complex, noisy and non-linear signals is a well-studied problem in the field of robotics. Using only off-the-shelf hardware, we achieve robust position estimation to within a meter in our experimental context and after adequate training of our system. We can also coarsely determine our orientation and can track our position as we move. By applying recent advances in probabilistic inference of position and sensor fusion from noisy signals, we show that the RF emissions from base stations as measured by off-the-shelf wireless Ethernet cards are sufficiently rich in information to permit a mobile device to reliably track its location. |
Ladd, A M; Bekris, K E; Marceau, G; Rudys, A; Kavraki, L E; Wallach, D S Using Wireless Ethernet for Localization Conference IEEE/RJS International Conference on Intelligent Robots and Systems (IROS02), Lausanne, Switzerland, 2002. Abstract | Links | BibTeX | Tags: @conference{wireless_ethernet_localization, title = {Using Wireless Ethernet for Localization}, author = {A M Ladd and K E Bekris and G Marceau and A Rudys and L E Kavraki and D S Wallach}, url = {http://www.cs.rutgers.edu/~kb572/pubs/wireless_ethernet_localization.pdf}, year = {2002}, date = {2002-09-01}, booktitle = {IEEE/RJS International Conference on Intelligent Robots and Systems (IROS02)}, address = {Lausanne, Switzerland}, abstract = {IEEE 802.11b wireless Ethernet is rapidly becoming the standard for in-building and short-range wireless communication. Many mobile devices such as mobile robots, laptops and PDAs already use this protocol for wireless communication. Many wireless Ethernet cards measure the signal strength of incoming packets. This paper investigates the feasibility of implementing a localization system using this sensor. Using a Bayesian localization framework, we show experiments demonstrating that off-the-shelf wireless hardware can accurately be used for location sensing and tracking with about one meter precision in a wireless-enabled office building.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } IEEE 802.11b wireless Ethernet is rapidly becoming the standard for in-building and short-range wireless communication. Many mobile devices such as mobile robots, laptops and PDAs already use this protocol for wireless communication. Many wireless Ethernet cards measure the signal strength of incoming packets. This paper investigates the feasibility of implementing a localization system using this sensor. Using a Bayesian localization framework, we show experiments demonstrating that off-the-shelf wireless hardware can accurately be used for location sensing and tracking with about one meter precision in a wireless-enabled office building. |
Bekris, K E; Hatzopoulos, K; Kazazakis, G; Kontolemakis, G; Masvoula, M; Tsivourakis, N; Argyros, A A; Trahanias, P PYTHEAS: An Integrated Robotic System with Autonomous Navigation Capabilities Journal Article Journal of Image Processing & Communications, 8 (2), 2002, (Special Issue on "Intelligent Sensing, Image Processing and Applications"). Abstract | Links | BibTeX | Tags: @article{pytheas, title = {PYTHEAS: An Integrated Robotic System with Autonomous Navigation Capabilities}, author = {K E Bekris and K Hatzopoulos and G Kazazakis and G Kontolemakis and M Masvoula and N Tsivourakis and A A Argyros and P Trahanias}, url = {http://www.cs.rutgers.edu/~kb572/pubs/pytheas.pdf}, year = {2002}, date = {2002-07-01}, journal = {Journal of Image Processing & Communications}, volume = {8}, number = {2}, chapter = {81-92}, abstract = {In this paper we present PYTHEAS, an integrated robotic software system that supports autonomous navigation capabilities. These include localization, workspace mapping, path planning and tracking, and obstacle avoidance. PYTHEAS enables mapping of an unknown indoor environment by exploiting sensory information extracted from a laser scanner. Based on this acquired environment representation, the system is able to navigate autonomously in the mapped workspace, avoiding at the same time dynamic obstacles, such as moving persons or other objects. The developed competences are coupled in an integrated system, which can be controlled through a user-friendly interface over the web. Experimental results demonstrate the ability of the developed system to map complicated environments and support navigation in dynamic worlds.}, note = {Special Issue on "Intelligent Sensing, Image Processing and Applications"}, keywords = {}, pubstate = {published}, tppubtype = {article} } In this paper we present PYTHEAS, an integrated robotic software system that supports autonomous navigation capabilities. These include localization, workspace mapping, path planning and tracking, and obstacle avoidance. PYTHEAS enables mapping of an unknown indoor environment by exploiting sensory information extracted from a laser scanner. Based on this acquired environment representation, the system is able to navigate autonomously in the mapped workspace, avoiding at the same time dynamic obstacles, such as moving persons or other objects. The developed competences are coupled in an integrated system, which can be controlled through a user-friendly interface over the web. Experimental results demonstrate the ability of the developed system to map complicated environments and support navigation in dynamic worlds. |
2001 |
Argyros, A A; Bekris, K E; Orphanoudakis, S C Robot Homing Based on Corner Tracking in a Sequence of Panoramic Images Conference Computer Vision and Pattern Recognition Conference (CVPR01), Hawaii, USA, 2001. Abstract | Links | BibTeX | Tags: @conference{homing_corner_tracking, title = {Robot Homing Based on Corner Tracking in a Sequence of Panoramic Images}, author = {A A Argyros and K E Bekris and S C Orphanoudakis}, url = {http://www.cs.rutgers.edu/~kb572/pubs/homing_corner_tracking.pdf}, year = {2001}, date = {2001-12-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. |
Bekris, K E; Hatzopoulos, K; Kazazakis, G; Kontolemakis, G; Masvoula, M; Tsivourakis, N; Argyros, A A; Trahanias, P PYTHEAS: An Integrated Robotic System with Autonomous Navigation Capabilities Conference KTISIVIOS Pan Hellenic Conference in Robotics and Automation, Santorini, Greece, 2001. Abstract | Links | BibTeX | Tags: @conference{pytheas_ktisivios, title = {PYTHEAS: An Integrated Robotic System with Autonomous Navigation Capabilities}, author = {K E Bekris and K Hatzopoulos and G Kazazakis and G Kontolemakis and M Masvoula and N Tsivourakis and A 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. |
0000 |
Chang, Haonan; Boyalakuntla, Kowndinya; Lu, Shiyang; Cai, Siwei; Jing, Eric; Keskar, Shreesh; Geng, Shijie; Abbas, Adeeb; Zhou, Lifeng; Bekris, Kostas E; Boularias, Abdeslam Context-Aware Entity Grounding with Open-Vocabulary 3D Scene Graphs Conference Conference on Robot Learning (CoRL), 0000. Abstract | Links | BibTeX | Tags: Learning, Robot Perception @conference{Chang_Corl23, title = {Context-Aware Entity Grounding with Open-Vocabulary 3D Scene Graphs}, author = {Haonan Chang and Kowndinya Boyalakuntla and Shiyang Lu and Siwei Cai and Eric Jing and Shreesh Keskar and Shijie Geng and Adeeb Abbas and Lifeng Zhou and Kostas E. Bekris and Abdeslam Boularias}, url = {https://openreview.net/pdf?id=cjEI5qXoT0}, booktitle = {Conference on Robot Learning (CoRL)}, abstract = {We present an Open-Vocabulary 3D Scene Graph (OVSG), a formal framework for grounding a variety of entities, such as object instances, agents, and regions, with free-form text-based queries. Unlike conventional semantic-based object localization approaches, our system facilitates context-aware entity localization, allowing for queries such as pick up a cup on a kitchen table or navigate to a sofa on which someone is sitting. In contrast to existing research on 3D scene graphs, OVSG supports free-form text input and open-vocabulary querying. Through a series of comparative experiments using the ScanNet dataset and a self-collected dataset, we demonstrate that our proposed approach significantly surpasses the performance of previous semantic-based localization techniques. Moreover, we highlight the practical application of OVSG in real-world robot navigation and manipulation experiments.}, keywords = {Learning, Robot Perception}, pubstate = {published}, tppubtype = {conference} } We present an Open-Vocabulary 3D Scene Graph (OVSG), a formal framework for grounding a variety of entities, such as object instances, agents, and regions, with free-form text-based queries. Unlike conventional semantic-based object localization approaches, our system facilitates context-aware entity localization, allowing for queries such as pick up a cup on a kitchen table or navigate to a sofa on which someone is sitting. In contrast to existing research on 3D scene graphs, OVSG supports free-form text input and open-vocabulary querying. Through a series of comparative experiments using the ScanNet dataset and a self-collected dataset, we demonstrate that our proposed approach significantly surpasses the performance of previous semantic-based localization techniques. Moreover, we highlight the practical application of OVSG in real-world robot navigation and manipulation experiments. |