That park set is using something like a camera and then edge detection/center of mass or something if I remember from class correctly.
So you could sort of do it with trees and a phone, but trees aren't on a normal o map so that doesn't make it fun.
My proposal was a small number of laser range finger measurements every so many meters. You could locate that way I think - that's not that much different than how one orienteers! I'm not sure if the prof will let us get away with only localization, then mapping would need a crapload more (unless trees) measurements, which then maybe the project teammates are right and it would be a pain.
At least we are all agreed that we want to work with something that doesn't have a lot of processing or measurement mess, which seems like the worst part of it.
Variables like time (of day) and bearings need a different set of statistics, for the reason that you have noted. This book is out of print, but if you can borrow a copy at your library, it's definitely worth a read. Very approachable, and useful.