This paper proposes a new heuristic search technique for obstacle avoidance of autonomous underwater vehicles that are equipped with a looking ahead obstacle avoidance sonar. Fuzzy relational method of Bandler and Kohout is used as the mathematical implementation for the analysis and synthesis of relations between the partitioned sections of sonar and the environmental properties. For the technique used in this paper, sonar range must be partitioned into multi equal sections and membership functions of the properties and the corresponding fuzzy rule bases are estimated by domain experts. The simulation result leads to the conclusion that only with the two properties safety and remoteness and with sonar partitioned in seven sections, the applied technique enables AUVs to safely avoid any obstacle and to navigate on the optimal way to goal.