  We report the detection of four new extra-solar planets from the
Anglo-Australian Planet Search orbiting the somewhat metal-enriched stars
HD73526, HD76700, HD30177 and HD2039. The planetary companion of HD 76700 has a
circular orbit with a period of 3.98d. With M sin i=0.197+-0.017 Mjup, or 0.69
times the mass of Saturn, is one of the lowest minimum mass extra-solar planets
yet detected. The remaining planets all have elliptical orbits with periods
ranging from 190.5d to 4.4yr. All four planets have been found orbiting stars
from a sub-sample of twenty metal-enriched and faint (V<9) stars, which was
added to the Anglo-Australian Planet Search's magnitude-limited V$<$7.5 main
sample in October 1998. These stars were selected to be metal-enriched on the
basis of their Stromgren photometry, and their enrichment has been subsequently
confirmed by detailed spectroscopic analysis.
