I don't understand the benefit to HATEOAS for APIs intended for use by programs (as opposed to humans directly browsing your API). Sure, the customer isn't bound to a URL schema but they are bound to a data schema which is the same thing in my mind.
For example, assume I want to view an item on an order, let's assume I've discovered or know the order URL already.
order = get(orderURL); item = get(order.itemURL);
order = get(orderURL); item = get(getItemURL(order,5));
In the first model I have to know the fact that the order object has an itemURL field. In the second model I have to know how to construct an item URL. In both cases I have to "know" something ahead of time so what is HATEOAS actually doing for me?