This research develops a new roadmap method for autonomous mobile robots based on variable-resolution partitioning of continuous state space. Unlike conventional roadmaps which include position information only, the proposed roadmap also includes velocity information. Each node of the proposed roadmap consists of a fixed position and a range of velocity values, where velocity ranges are determined by variable-resolution partitioning of velocity space. An ordered pair of nodes are connected by a directed link if any combination of velocity values within the ranges represented by the nodes produce a trajectory satisfying a set of safety constraints. In this manner, an executable trajectory connecting arbitrary starting node and destination node is obtained by applying a graph search technique on the proposed roadmap. The proposed method is evaluated through simulations.