In the context of robotics, configuration space (cspace) is widely used for non-circular robots to engage tasks such as path planning, collision check, and motion planning. In many real-time applications, it is important for a robot to give a quick response to the user’s command. Therefore, a constant bound on planning time per action is severely imposed. However, existing search algorithms used in c-space gain first move lags which vary with the size of the underlying problem. Furthermore, applying real-time search algorithms on c-space maps often causes the robots being trapped within local minima. In order to solve the above mentioned problems, we extend the learning real-time search (LRTS) algorithm to search on a set of c-space generalized Voronoi diagrams (c-space GVDs), helping the robots to incrementally plan a path, to efficiently avoid local minima, and to execute fast movement. In our work, an incremental algorithm is firstly proposed to build and represent the c-space maps in Boolean vectors. Then, the method of detecting grid-based GVDs from the c-space maps is further discussed. Based on the c-space GVDs, details of the LRTS and its implementation considerations are studied. The resulting experiments and analysis show that, using LRTS to search on the c-space GVDs can 1) gain smaller and constant first move lags which is independent of the problem size; 2) gain maximal clearance from obstacles so that collision checks are much reduced; 3) avoid local minima and thus prevent the robot from visually unrealistic scratching.