How can a windows service programmatically restart itself?

Dim proc As New Process()
Dim psi As New ProcessStartInfo()

psi.CreateNoWindow = True
psi.FileName = "cmd.exe"
psi.Arguments = "/C net stop YOURSERVICENAMEHERE && net start YOURSERVICENAMEHERE"
psi.LoadUserProfile = False
psi.UseShellExecute = False
psi.WindowStyle = ProcessWindowStyle.Hidden
proc.StartInfo = psi
proc.Start()

const string strCmdText = "/C net stop \"SERVICENAME\"&net start \"SERVICENAME\"";
Process.Start("CMD.exe", strCmdText);

where SERVICENAME is the name of your service (double quotes included to account for spaces in the service name, can be omitted otherwise).

Clean, no auto-restart configuration necessary.

Set the service to restart after failure (double click the service in the control panel and have a look around on those tabs - I forget the name of it). Then, anytime you want the service to restart, just call Environment.Exit(1) (or any non-zero return) and the OS will restart it for you.

You can't be sure that the user account that your service is running under even has permissions to stop and restart the service.