In this paper, we propose Q-learning with adaptive state space construction. This provides an efficient method to construct the state space suitable for Q-learning to accomplish the task in continuous sensor space. In the proposed algorithm, a robot starts with single state covering whole sensor space. A new state is generated incrementally by segmenting a sub-region of the sensor space or combining the existing states. The criterion for incremental segmentation and combination is derived from Q-learning algorithm. Simulation results show that the proposed algortithm is able to construct the sensor space effectively to accomplish the task. The resulting state space reveals the sensor space in a Voronoi tessellation.