I studied the question a little, and it depends on how it is packaged.
If you start Fast Downward as a subprocess, you are technically not linking with it, and ask the system (a component that is out of your hands) to start it for you.
In theory that serves as an interface that allows Fast Downward to be replaced by anything else, and therefore the dependency is legitimately looser, so the license of the program must not contaminate.
That is why ROSPlan embeds binaries of planners directly, but can still pretend to the BSD license!
You could do the same.
However it is open to debate in the GNU community whether a system packaging GPL binaries out of the box should be GPL.
Some argue that as soon as you provide an app that embeds a GPL binary and it is pre-configured to use it, even via a subprocess, GPL should propagate.
Like anything pre-installed on a Linux would become GPL by these standards.
But this is a marginal claim, and the consensus is that GPL do not propagate in these conditions.
In the case of Fast Downward for Android, it is a service provided by a separate app, so your app does not embed it.
So even with pretty high standards, the GPL license does not propagate to your app.
In turn, it is not
perfectly guaranteed to get the real Fast Downward when it uses the
service interface.
Something or someone else bears the responsibility to make
sure it is installed.