This looks like a product / adb issue.
Provisionally belongs to the sheriff, until they can decide whether the arc constable should handle this instead.

+ Arc constable

Digging into https://cros-goldeneye.corp.google.com/chromeos/healthmonitoring/buildDetails?buildbucketId=8926162619319790400

test logs at https://stainless.corp.google.com/browse/chromeos-autotest-results/270540766-chromeos-test/

Failure symptom is slightly different from the one mentioned in OP:

INFO	----	----	kernel=3.14.0	localtime=Dec 25 07:54:09	timestamp=1545753249	
START	----	----	timestamp=1545753271	localtime=Dec 25 07:54:31	
	START	cheets_CleanShutDown	cheets_CleanShutDown	timestamp=1545753271	localtime=Dec 25 07:54:31	
		ERROR	cheets_CleanShutDown	cheets_CleanShutDown	timestamp=1545753284	localtime=Dec 25 07:54:44	Command <adb shell 'pgrep -c -f org.chromium.arc.intent_helper'> failed, rc=255, Command returned non-zero exit status
	END ERROR	cheets_CleanShutDown	cheets_CleanShutDown	timestamp=1545753284	localtime=Dec 25 07:54:44	
END GOOD	----	----	timestamp=1545753288	localtime=Dec 25 07:54:48	

Looking at the autotest logs, I think ADB is stopping Android container from exiting. There's an ADB change that went in yesterday which could be the culprit.

recardoq@, Can you confirm please?

CL: https://chromium-review.googlesource.com/c/catapult/+/1386564

nednguyen@: taking a look at it

OTOH, hana-paladin from the same master-paladin run failed with the exception in OP: https://cros-goldeneye.corp.google.com/chromeos/healthmonitoring/buildDetails?buildbucketId=8926162544225427712

Perhaps #2 needs a separate bug? In the same master-paladin run, for the same test, android failed to boot for one model, while it failed to shutdown for a different model.

Why do you think CL https://chromium-review.googlesource.com/c/catapult/+/1386564 is related? 

I don't think it's related to android or ChromeOS failure 

build started to fail in 11466: http://stainless/search?view=matrix&row=model&col=build&first_date=2018-12-20&last_date=2018-12-26&test=cheets_CleanShutDown&exclude_cts=false&exclude_not_run=false&exclude_non_release=true&exclude_au=true&exclude_acts=true&exclude_retried=true&exclude_non_production=false

only change in 11466 comes from ChromeOS:
https://crosland.corp.google.com/log/11465.0.0..11466.0.0

and that is a bot-commit that changed the post-submit package:
https://chrome-internal.googlesource.com/chromeos/overlays/overlay-caroline-private/+/43bb1c1073b71490afad1dedb1a238cdff0b54f7%5E%21/

I downloaded rc2 and rc3 from GS and the only change was here:
-PATH: board/caroline/postsubmit-R73-11464.0.0-rc/packages/chromeos-base/arc-networkd-0.0.1-r1330.tbz2
+PATH: board/caroline/postsubmit-R73-11464.0.0-rc/packages/chromeos-base/arc-networkd-0.0.1-r1331.tbz2

And that changed was reverted here:
https://crrev.com/c/1390396

waiting for next build to see if that fixes the issue.

reassigning to non-pst arc constable:
hashimoto@ reassign it back to me if you can't fix it in your shift.

Seems this is not fixed yet.
Reverted https://crrev.com/c/1390740 too.

Tried locally with a veyron_minnie and cheets_CleanShutDown started passing with the revert mentioned in comment #13.

comment#14.
yes, thanks. build r73-11476 is green regarding cheets_CleanShutDown:
http://stainless/search?view=matrix&row=model&col=build&first_date=2018-12-21&last_date=2018-12-27&test=%5Echeets%5C_CleanShutDown%24&exclude_cts=false&exclude_not_run=false&exclude_non_release=true&exclude_au=true&exclude_acts=true&exclude_retried=true&exclude_non_production=false

but PFQ is still red failing with the same error... strange. waiting for the next build.

closing bug as last PFQ is green:
http://cros-goldeneye/chromeos/legoland/builderSummary?builderGroups=mst_android_pfq%2Cnyc_android_pfq%2Cpi_android_pfq&limit=3&buildBranch=master

the revert in comment#13 seems to have fixed it.