Detection and identification of faulty measurements like multipath is of prime importance for radio-navigation. A method based on interval analysis and constraint propagation is presented in this paper and applied to GPS positioning. This method is able to detect and identify erroneous measurements in real-time simultaneously with the computation of the positioning domain. With bounded-error measurements (GPS pseudoranges on visible satellites here), fault-detection is guaranteed not to trigger false alarms. A q-relaxed robust estimation method is studied. By the use of a breadth-first exploration strategy and of measurement consistency counters, the algorithm can promptly signal a detected fault during the set-inversion process. It can also be stopped at any time of the evaluation, and can instantly return the solution subpaving and the list of identified erroneous measurements. We demonstrate than the method is able to handle simultaneous faults as long as they are fewer than the degree of relaxation. The method has been evaluated with real GPS pseudodistances in an urban environment with a low-cost high-sensitivity GPS receiver providing numerous faulty multipath measurements and we report experiments. As the application of this method deals with road vehicles, a 3-D map of the drivable space has also been used to constrain the vehicle location to improve the performance of the method.