Hello hello. I'm in the preliminary design phase for a space based game, and I need some advice on how to approach the AI side of things.

Here's the situation in a nutshell. Say I'm a space explorer with a spaceship, and I am competing with other space explorers to be the first one to discover things. I have a procedurally generated 2D top-down solar system, and to make things a little simpler, let's say all the planets in the system are static, meaning they are not orbiting their sun. But they all have their gravity wells of varying strength. As a player I have to negotiate newtonian physics around these planets, using engine thrust at the right amounts and timing, to get to where I want. That part is not a problem. I'm also willing to assume non-newtonian rotation so that AI and player do not need to account for appyling torque to get a correct bearing.

So far I have not mentioned whether this is real-time or turn-based and that's because of my uncertainty around AI.

Problem is I'm not sure how to approach the AI side of things either way. Ideally I'd like to have an AI that can optimize trajectory for speed and/or fuel efficiency, but I have been able to find precious little on the topic on the interwebs. The best I've found so far is the following article from a decade ago, and it does not really point to a solution: http://playtechs.blogspot.ca/2007/05/pathfinding-in-space.html

If I can find a good resource on how to pull this off in realtime, I'd like to go that route. At the moment my fallback is using a turn based system for exploration and visualizing the system as a hex grid. Then using A* I could get AI agents to naively assume use of thrust to come to a stand still each time they want to change trajectory, and then add extra thrust to move in the next direction, but I'm worried this would be extremely under-optimized in terms of fuel efficiency and the reach of rival ships as a result. I could also factor in the AI ship's current velocity into the graph search, which would likely greatly increase the search space for pathfinding, but I haven't experimented with it yet to be able to say whether it's viable.

Any thoughts?

As you say, you can make an A* search with newtonian physics, in fact, I saw one of these in GIT (a python open sourced project).
You can find the "optimal solution" given de discretization... and yes, you have to discretize rotation, thrust, etc. so then you can scale things. There's a lot of information out there, some time ago I glased over a bunch of papers related to spaceships and wave riding ships (real ships) doing this kind of search... So I think you're taking the safe path, and you're doing well, you can find more information if you really search for it. 

I think you can optimize for fuel consumption, partially, at least. But I think I get your problem, maybe the search grows too much. Then Evolution maybe? 

Discritization works well, you got it right, unless you want to go into the research part of things (there's a lot to test).