Estimating an occupant's location is arguably the most fundamental sensing task in smart buildings. Existing indoor tracking systems require occupants to carry specialized devices or install programs on their smartphones to collect inertial sensing data. In this paper, we propose MapSentinel, which performs non-intrusive location sensing based on WiFi access points and ultrasonic sensors. MapSentinel also combines the noisy sensor readings with the floormap information. Instead of using floormap merely to conduct sanity check of walking trajectories, we exploit the motion characteristics of occupants available from the floormap to enhance our location estimation. The fusion of heterogeneous information is theoretically formulated within the Factor Graph framework and the inference algorithm based on Particle Filtering is developed to efficiently solve real-time walking trajectories. Our evaluation in a large office space shows that the MapSentinel can achieve significant accuracy improvements compared with the purely WiFi-based tracking system.