First, is it possible to build map without landmarks for a robot in 2D? Let's say we have an aisle surrounded by two walls. The robot moves in this environment. Now is it feasible to build such a SLAM problem? Or landmarks must be available to do so?
I think you misunderstand what a landmark is. It is a generic, catch-all term for anything that a robot can recognize and use as part of a map. In particular, "landmarks" are important for feature-based SLAM algorithms, such as EKF-based slam. What you use for "landmarks" depends on what sensors are available to the robot.
In your case, since you haven't specified any sensing, then we'll assume the robot knows when it hits an object. Then any "landmark" is simply any time the robot bumps into something. If you do this with pen and paper, you'd just wander around and put an X any time you hit something, then turn and keep wandering. As time goes to infinity, you'd have a reasonable map of where object boundaries are, and what the object shapes are, as long as everything is static.
In this case, the "map" can just be a bitmap, where each pixel is 0 or 1, depending on if it has an object in that space or not. Scaling is up to the application.
I suggest doing a bit more research on these topics:
- Occupancy Grid representation
- Feature-based mapping
I think it is necessary to define what a landmark actually is. The other answer just defines them as markers and gives some examples. Something more formal and distinctive would be the following:
Landmarks are features which can easily be re-observed and distinguished from the environment. They are used by the robot to find out where it is (to localize itself).
Landmarks should be easily re-observable. Individual landmarks should be distinguishable from each other. Landmarks should be plentiful in the environment. Landmarks should be stationary.
This would for example exclude a simple pixel to act as a landmark, since in the real world it corresponds to an object which will become more or less pixels depending on distance. A blob would be more suitable since we just rely on finding a closed shape of a certain color (again with some threshold because colors change depending on lightening conditions and angle). In the real world the blob would be some orange sticker attached to the wall for example.
I just posted a similar question, trying to locate a paper than a co-worker remembered (ICRA? 2011? Not from Mudd nor the Foxe paper). I'd second @JustSomeHelp -- they need to be distinguishable. So a bump sensor alone won't help as you'll basically have (in naive form), one landmark that keeps getting different locations. That's going to end badly.
Clearly though, the recti-linear assumption is super helpful -- there's a 99 paper that address this. However I've not yet found a canonical approach to doing it
Z. J. Butler, A. A. Rizzi, and R. L. Hollis. Contact sensor-based coverage of rectilinear environments. In Proc. of IEEE Int’l Symposium on Intelligent Control, 1999.