This study develops a trajectory generation method for mobile robots and autonomoous vehicles that utilizes pre-computed map information of the environment. The state space (configuration space) of a mobile robot model is partitioned into intervals (boxes). A transition is defined from one box to another if a robot can travel from any configuration in the first box to any configuration in the second box. The boxes are subdivided into smaller boxes if necessary. In this manner, we obtain a "map" of an environment that consists of configuration boxes in multiple resolutions. This map can be utilized in the path planning phase for generating a trajectory connecting two configurations while satisfying physical constraints by computing graph search on the map.

移動ロボットや自動走行車などの移動体の高速な軌道生成を可能とする地図情報の表現形式やその計算方法を研究しています． ロボットモデルの状態空間（コンフィギュレーション空間）を区間分割し，ある区間中の任意の状態から別の区間の任意の状態へ，種々の物理的制約を満たして 移動可能である場合に区間から区間への遷移を定義します．区間分割が粗く，判定ができない場合は区間を細分化します． このようにして，ある環境に対してロボットの移動性を考慮した「地図」を生成しておくことにより， 物理制約を満たしながら二点間を結ぶ軌道をグラフ探索により求めることが可能となります．

A number of waypoints are placed in the environment, and the configuration space of the vehicle at each waypoint is divided into multiple intervals. Each pair of intervals is checked whether the vehicle can travel between the corresponding waypoints with terminal configurations chosen arbitrarily from these intervals. When the check result is ambiguous, then these intervals are subdivided into smalle ones. This map information can be utilized in the path planning phase to generated physical feasible trajectories by means of graph search.

環境中に予め配置した経由点状でのロボットの状態（方位角や速度など）の空間を区間分割し， 各区間の組について，ロボットが速度制約などの制約条件を満足しつつ経由点間を移動可能であるかを 判定します．判定があいまいである場合は区間をより細かく分割します． この手続きを事前に行うことにより，任意の経由点間を結ぶ軌跡をグラフ探索により効率的に 計算することが可能となります．

全方向移動ロボットモデルに対して速度空間を分割した場合	操舵型移動ロボットモデルに対して方位空間を分割した場合
An omni-directional mobile robot. The velocity space is expressed by boxes.	A car-like mobile robot. The orientation space is expressed by intervals.

The multi-resolution map technique is applied to autonomous parking. Parking is challenging to both human drivers and autonomos cars because i) a car must be steered to a narrow parking spot while avoiding other obstacles with very small margins, ii) the moving direction of a car must be switched between forward and reverse if necessary, and iii) trajectories with very large curvature must be utilized considering the limitation of steering angle. One solution to these problems is to construct an intelligent parking system that makes use of a digital map of the parking lot. When a car enters the parking lot, the system quickly generates a reference trajectory to a parking spot by using a map, and sends that data to the car via wireless network. Then the car can by navigated to the parking spot just by tracking the provided reference trajectory.

多分解能地図技術を自動駐車に応用しました． 駐車は以下の理由から人間の運転者と自動運転車の両方にとって難しい運転タスクの一つです． i) 障害物を小さなクリアランスで回避しながら車両を駐車スペースへ移動しなければならない， ii) 必要に応じて前進と後退を切り換えなければならない， iii) 操舵角限界を考慮して高曲率の軌道を用いる必要がある． 駐車場自体にデジタル地図情報を持たせることで，駐車場を訪れた車に駐車スペースへの軌跡を生成し， 提供する機能を付与した「インテリジェント駐車場」を構築することが考えられます．

Map of a parking lot. This includes the layout of parking spots, obstacles, and guidelines.	Guidelines are partitioned in multiple-resolutions and executabe trajectories between pairs of guidelines are precomputed.