In the context of touch-based object localisation, solving the problem of “where to sense next” is a challenging task due to the curse of dimensionality related to belief-state reasoning. We present a constrained optimisation scheme that computes the next best action maximising the trade off between (i) the localisation information gain, (ii) the time required for its computation, and (iii) the motion-execution time. This allows the robot programmer to have a deterministic influence on the length of every sensing action. The proposed methodology is applied to localise a solid object in 3D using a Staubli RX90 robot equipped with a force-torque sensor coupled with a spherical end effector. A case-study comparison of the task executed with two different time constraints is presented.