Here is some guaranteed steps that will help, I had the same issue and I had to figure out myself, follow the steps exactly as shown below :
1- Delete the android auto from you phone
2- Go to Bluetooth setting and delete your car paired device.
3- Go to your car head unit settings and delete...