This paper presents a novel movement planning algorithm for a guard robot in an indoor environment, imitating the job of human security. A movement planner is employed by the guard robot to continuously observe a cert...This paper presents a novel movement planning algorithm for a guard robot in an indoor environment, imitating the job of human security. A movement planner is employed by the guard robot to continuously observe a certain person. This problem can be distinguished from the person following problem which continuously follows the object. Instead, the movement planner aims to reduce the movement and the energy while keeping the target person under its visibility. The proposed algorithm exploits the topological features of the environment to obtain a set of viewpoint candidates, and it is then optimized by a cost-based set covering problem. Both the robot and the target person are modeled using geodesic motion model which considers the environment shape. Subsequently, a particle model-based planner is employed, considering the chance constraints over the robot visibility, to choose an optimal action for the robot. Simulation results using 3D simulator and experiments on a real environment are provided to show the feasibility and effectiveness of our algorithm.展开更多
We study the problem of searching for a mobile intruder in a polygonal region P by two guards. The objective is to decide whether there should exist a search schedule for the two guards to detect the intruder, no matt...We study the problem of searching for a mobile intruder in a polygonal region P by two guards. The objective is to decide whether there should exist a search schedule for the two guards to detect the intruder, no matter how fast the intruder moves, and if so, generate a search schedule. During the search, the two guards are required to walk on the boundary of P continuously and be mutually visible all the time. We present a characterization of the class of polygons searchable by two guards in terms of non-redundant components, and thus solve a long-standing open problem in computational geometry. Also, we give an optimal O（n） time algorithm to determine the two-guard searchability in a polygon, and an O（n log n ＋ m） time algorithm to generate a search schedule, if it exists, where n is the number of vertices of P and m （≤ n^2） is the number of search instructions reported.展开更多
This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually ＂see＂ an intruder that is unpredictable and capable of moving arbitrarily fast. A searcher is called the boun...This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually ＂see＂ an intruder that is unpredictable and capable of moving arbitrarily fast. A searcher is called the boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher. Based on our characterization, the equivalence of the ability of the searchers having only one flashlight and the one of the searchers having full 360° vision is simply established, and moreover, an optimal O（n） time and space algorithm for determining the searchability of simple polygons is obtained. We also give an O（n log n ＋ I） time algorithm for generating a search schedule if it exists, where I （〈 3n^2） is the number of search instructions reported. Our results improve upon the previously known O（n^2） time and space bounds.展开更多
文摘This paper presents a novel movement planning algorithm for a guard robot in an indoor environment, imitating the job of human security. A movement planner is employed by the guard robot to continuously observe a certain person. This problem can be distinguished from the person following problem which continuously follows the object. Instead, the movement planner aims to reduce the movement and the energy while keeping the target person under its visibility. The proposed algorithm exploits the topological features of the environment to obtain a set of viewpoint candidates, and it is then optimized by a cost-based set covering problem. Both the robot and the target person are modeled using geodesic motion model which considers the environment shape. Subsequently, a particle model-based planner is employed, considering the chance constraints over the robot visibility, to choose an optimal action for the robot. Simulation results using 3D simulator and experiments on a real environment are provided to show the feasibility and effectiveness of our algorithm.
基金supported by the Grand-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan, and a research grant from Tokai University.
文摘We study the problem of searching for a mobile intruder in a polygonal region P by two guards. The objective is to decide whether there should exist a search schedule for the two guards to detect the intruder, no matter how fast the intruder moves, and if so, generate a search schedule. During the search, the two guards are required to walk on the boundary of P continuously and be mutually visible all the time. We present a characterization of the class of polygons searchable by two guards in terms of non-redundant components, and thus solve a long-standing open problem in computational geometry. Also, we give an optimal O（n） time algorithm to determine the two-guard searchability in a polygon, and an O（n log n ＋ m） time algorithm to generate a search schedule, if it exists, where n is the number of vertices of P and m （≤ n^2） is the number of search instructions reported.
文摘This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually ＂see＂ an intruder that is unpredictable and capable of moving arbitrarily fast. A searcher is called the boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher. Based on our characterization, the equivalence of the ability of the searchers having only one flashlight and the one of the searchers having full 360° vision is simply established, and moreover, an optimal O（n） time and space algorithm for determining the searchability of simple polygons is obtained. We also give an O（n log n ＋ I） time algorithm for generating a search schedule if it exists, where I （〈 3n^2） is the number of search instructions reported. Our results improve upon the previously known O（n^2） time and space bounds.
