Upper bounds on the average distance $\overline{l}$ between pairs of vertices of a connected graph with given order $n$ and minimum degree $\delta$ are studied. The AutoGraphiX system for conjecture making is used to generate such bounds when the minimum degree is at least 2, 3, 4 or 5. A sharp bound is proved when $\delta \ge 2$ and conjectures are provided in the remaining three cases. Two more conjectures are given for particular cases, namely, when $n = (\delta +1)k$ and $n=(\delta +1)k +2$ for some integer $k \ge 2$.