IANAL - If my reading of business history is of any service, you build your software or demo (you don't need a patent to tinker as long as you aren't distributing it or selling it or making money of it.) Then you demo it to those with blocking patents you've had to incorporate in your work. (Hopefully you have tech you can patent.) Then you negotiate.
Remember, patents can only be obtained for methods, not results - so in theory if you can find a new method to accomplish what they did, that's cool, you just got around their patent. (This is what Watt of steam engine fame did, in the end, when negotiations for patented tech he really needed proved futile. Took him a while to come up with a parallel invention or two he needed.)
So as noted, these negotiations can go very wrong - or proceed very well.
Find out what patent exchanges have already happened between the relevant companies. If, as is frequently the case, a number of companies have the rights to the whole palette of patents blocking you thanks to those rights swaps, you may only have to make one deal, with any one of those companies and can therefore take the best offer, playing each company off against the others. For a final deal to distribute your software through them, say.
Note that FRAND patents won't be a barrier to you. (Unless someone wants to break the law to thwart you, and that's happened too.)