In this paper, we present a new approach to human-aware robot navigation, which extends our previous proximity-based navigation framework [1] by introducing visibility and predictability as new parameters. We derived these parameters from a user study and incorporated them into a cost function, which models the user’s discomfort with respect to a relative robot position based on proximity, visibility, predictability, and work efficiency. We use this cost function in combination with an A* planner to create a user-preferred robot navigation policy. In comparison to our previous framework, our new cost function results in a 6% increase in social distance compliance, a 6.3% decrease in visibility of the robot as preferred, and an average decrease of orientation changes of 12.6◦ per meter resulting in better predictability, while maintaining a comparable average path length. We further performed a virtual reality experiment to evaluate the user comfort based on direct human feedback, finding that the participants on average felt comfortable to very comfortable with the resulting robot trajectories from our approach.