[Marcus Vilain]

Hi all,
Not sure it's the right place for this very first question but here it is :
Suppose i'm solving a problem using the A* algorithm (let's call it A1)
Suppose now, that for each successor s of a node n, I need to start another A* algorithm (let's call it A2)
How the cost c returned by A2 must be used to correctly guide the search in A1 ? Is it the g cost of A1, the h cost of A1 ? a part of g or h ?
Thanks,
Marcus

[infurl]

What's the application that you are working on? Homework? Computer game? World domination?

The defining characteristic of the A* heuristic is that it must consistently underestimate the remaining cost in order to converge on a solution. It sounds like you are describing the iteratively deepening search variant (the others being breadth-first and depth-first search) but the heuristic remains the same.

[Marcus Vilain]

Hi,

I work on a planification problem:
Tasks are to be done. A1 tries to affect these tasks to computers.

Thus, a node in A1 represents a possible affectation (or not...  At this step we only make assumptions).

Then, this possibly feasible affectation is submitted to A2.

The most important fact is that we try to call A2 the less possible.

Thank you







Envoyé de mon iPhone en utilisant Tapatalk

[infurl]

That sounds like very interesting work. By "affect" do you mean "assign" or have I misunderstood you?

A generic planning algorithm such as A* might not be the best way to tackle what sounds like a scheduling problem. If scheduling is dynamic then there are a number of well documented approaches employed in multi-tasking operating systems that ought to scale up to distributed systems. Alternatively, if tasks are well defined and scheduling can be calculated ahead of time then maybe the Simplex algorithm would be more applicable.

[Marcus Vilain]

You’re right. «affectation Â» means « assignation Â».

The fact is that for now, the potential affectations are done by a CSP solver.

Only a subset of theses potential affectations are submitted to A2.

The question is : to be homogeneous, can this CSP be replaced by a A* algorithm (but from you previous post, it seems that this is maybe not a so good idea...) ? If so, how the cost computed by A2 can be used in A1 ?

Marcus






A1 is not a A* but a CSP

[infurl]

Constraint Satisfaction Problems are the more general case. Searching a problem space is just one kind of algorithm that may be used to solve a CSP. As far as achieving homogeneity is concerned, if the problem can be solved by searching a problem space then you can do it using an iteratively deepening A* search. That will combine all your searches into one homogeneous solution.

However you stated the problem was one of assigning tasks to computers, so that's a scheduling or resource allocation problem which would be handled differently. If you already know what tasks have to be performed then you don't need search, you need a different kind of CSP algorithm such as bin-packing or resource levelling. Consider the following questions.

Do the tasks have dependencies?
i.e. Does Task X have to be completed before Task Y can start?

Are the resources (computers) specialised?
i.e. Can some tasks only be performed by some computers?
You might have to use resource-levelling.

Do the tasks take a predictable or an unpredictable amount of time?
If the former then you can pre-calculate an optimal solution using Simplex.
If the latter then you will have to use a dynamic scheduling algorithm.

[Marcus Vilain]

Yes, tasks have logical dependencies ( task a if and only if task b) and temporal (before, after, starts at the same time ... )

Computers are specialized (a task can be made more or less efficiently/quickly by a computer). A computer cannot make some tasks)

To get the whole picture, see these computers as embedded in robots that need to be at certain places to full fill each task.

Don’t know enough about IDA*, I need to take a look... tomorrow !

Thanks

[spydaz]

Hi all,
Not sure it's the right place for this very first question but here it is :
Suppose i'm solving a problem using the A* algorithm (let's call it A1)
Suppose now, that for each successor s of a node n, I need to start another A* algorithm (let's call it A2)
How the cost c returned by A2 must be used to correctly guide the search in A1 ? Is it the g cost of A1, the h cost of A1 ? a part of g or h ?
Thanks,
Marcus

This is a recursive algorithm!

You need to explain it clearly so the algorithm can be defined properly;

Recursive algorithms are solved with Do while/Until loops using your if / then logic to test for the Condition.using a function to call itself.

[/font]